Description

There is a row with N blocks. Blocks are numbered from left to right in 1-based indexing. The i-th block's value is a_i.

First you have to sort these blocks by their value in increasing order. So the order of blocks may be changed after sorting.

Then you need to execute Q operations. There are two kinds of operations:​

1. Let m = N' divided by 2 rounding up, where N' is the number of blocks now. Then remove the m-th block.
2. Output the k-th block's value. Then divide all the blocks' value by 2 rounding down.

It's guaranteed that the first type of operations appears at most N - 1 times(i.e there must be at least one block all the time).

 

Note: be careful of the efficiency of your strategy. And the difference between rounding up and rounding down is to carry or to chop the remainder. For instance:

• 5 divided by 2 rounding up is equal to 3
• 5 divided by 2 rounding down is equal to 2

Input

The first line contains one integer N (1 ≤ N ≤ 10⁵) – the number of blocks.

The second line contains N integers a₁, a₂, ..., a_N (0 ≤ a_i ≤ 10¹⁸) – the value of each block.

The third line contains one integer Q (1 ≤ Q ≤ 10⁵) – the number of operations you need to execute.

Then Q lines follow. The i+3-th line contains one integer type_i (1 ≤ type_i ≤ 2) – the type of operations you need to execute. If type_i = 2 then one integer k (1 ≤ k ≤ N', where N' is the number of blocks then) follows.

 

It's guaranteed that:

• The 1st testcase must be as same as Sample below
• For the testcases 2 and 3: 1 ≤ N, Q ≤ 3000
• For the testcases 4 and 5: the number of the 2nd type operations ≤ 60
• For the testcases 6: a_i ≤ 60

Output

For every 2nd type operations, output the k-th block's value then.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss