15266번 - Intrinsic Interval 다국어

문제

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 π_a^b = (π_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 π₃⁶ is an interval (it contains the numbers 4 through 7) while π₁³ is not.

For a subsequence π_x^y its intrinsic interval is any interval π_a^b 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 π₁, π₂, . . . , π_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 x_j and y_j (1 ≤ x_j ≤ y_j ≤ n) — the endpoints of the j-th subsequence.

출력

Output m lines. The j-th line should contain two integers a_j and b_j where 1 ≤ a_j ≤ b_j ≤ n — the endpoints of some intrinsic interval of the j-th subsequence π_xj^y_j.

제한

힌트