시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 126 | 48 | 37 | 41.573% |
Given a permutation π of integers 1 through n, an interval in π is a consecutive subsequence consisting of consecutive numbers. More precisely, for indices a and b where 1 ≤ a ≤ b ≤ n, the subsequence πab = (πa, πa+1, . . . , πb) is an interval if sorting it would yield a sequence of consecutive integers. For example, in permutation π = (3, 1, 7, 5, 6, 4, 2), the subsequence π36 is an interval (it contains the numbers 4 through 7) while π13 is not.
For a subsequence πxy its intrinsic interval is any interval πab that contains the given subsequence (a ≤ x ≤ y ≤ b) and that is, additionally, as short as possible. Of course, the length of an interval is defined as the number of elements it contains.
Given a permutation π and m of its subsequences, find some intrinsic interval for each subsequence.
The first line contains an integer n (1 ≤ n ≤ 100 000) — the size of the permutation π. The following line contains n different integers π1, π2, . . . , πn (1 ≤ πj ≤ n) — the permutation itself.
The following line contains an integer m (1 ≤ m ≤ 100 000) — the number of subsequences. The j-th of the following m lines contains integers xj and yj (1 ≤ xj ≤ yj ≤ n) — the endpoints of the j-th subsequence.
Output m lines. The j-th line should contain two integers aj and bj where 1 ≤ aj ≤ bj ≤ n — the endpoints of some intrinsic interval of the j-th subsequence πxjyj.
7 3 1 7 5 6 4 2 3 3 6 7 7 1 3
3 6 7 7 1 7
10 2 1 4 3 5 6 7 10 8 9 5 2 3 3 7 4 7 4 8 7 8
1 4 3 7 3 7 3 10 7 10