Two Sequences solution codeforces

Two Sequences solution codeforces

Consider an array of integers C=[c1,c2,,cn]C=[c1,c2,…,cn] of length nn. Let’s build the sequence of arrays D0,D1,D2,,DnD0,D1,D2,…,Dn of length n+1n+1 in the following way:

• The first element of this sequence will be equals CCD0=CD0=C.
• For each 1in1≤i≤n array DiDi will be constructed from Di1Di−1 in the following way:
• Let’s find the lexicographically smallest subarray of Di1Di−1 of length ii. Then, the first nin−i elements of DiDi will be equals to the corresponding nin−i elements of array Di1Di−1 and the last ii elements of DiDi will be equals to the corresponding elements of the found subarray of length ii.

Array xx is subarray of array yy, if xx can be obtained by deletion of several (possibly, zero or all) elements from the beginning of yy and several (possibly, zero or all) elements from the end of yy.

For array CC let’s denote array DnDn as op(C)op(C).

Alice has an array of integers A=[a1,a2,,an]A=[a1,a2,…,an] of length nn. She will build the sequence of arrays B0,B1,,BnB0,B1,…,Bn of length n+1n+1 in the following way:

• The first element of this sequence will be equals AAB0=AB0=A.
• For each 1in1≤i≤n array BiBi will be equals op(Bi1)op(Bi−1), where opop is the transformation described above.

She will ask you qq queries about elements of sequence of arrays B0,B1,,BnB0,B1,…,Bn. Each query consists of two integers ii and jj, and the answer to this query is the value of the jj-th element of array BiBi.

Input

The first line contains the single integer nn (1n1051≤n≤105) — the length of array AA.

The second line contains nn integers a1,a2,,ana1,a2,…,an (1ain1≤ai≤n) — the array AA.

The third line contains the single integer qq (1q1061≤q≤106) — the number of queries.

Each of the next qq lines contains two integers iijj (1i,jn1≤i,j≤n) — parameters of queries.

Output

Output qq integers: values of Bi,jBi,j for required iijj.

Example

input

Copy
4
2 1 3 1
4
1 1
1 2
1 3
1 4


output

Copy
2
1
1
3

Note

In the first test case B0=A=[2,1,3,1]B0=A=[2,1,3,1].

B1B1 is constructed in the following way:

• Initially, D0=[2,1,3,1]D0=[2,1,3,1].
• For i=1i=1 the lexicographically smallest subarray of D0D0 of length 11 is [1][1], so D1D1 will be [2,1,3,1][2,1,3,1].
• For i=2i=2 the lexicographically smallest subarray of D1D1 of length 22 is [1,3][1,3], so D2D2 will be [2,1,1,3][2,1,1,3].
• For i=3i=3 the lexicographically smallest subarray of D2D2 of length 33 is [1,1,3][1,1,3], so D3D3 will be [2,1,1,3][2,1,1,3].
• For i=4i=4 the lexicographically smallest subarray of D3D3 of length 44 is [2,1,1,3][2,1,1,3], so D4D4 will be [2,1,1,3][2,1,1,3].
• So, B1=op(B0)=op([2,1,3,1])=[2,1,1,3]B1=op(B0)=op([2,1,3,1])=[2,1,1,3].