The operations that are performed in a data structure can be categorized into two types: query and update. A query operation usually answers some specific questions about the stored data. An update usually adds data or changes the state of data in the structure. For example, adding an element or deleting the top element of a stack are update operations. While, accessing the top element is a query operation.
In this problem, you are asked to design a data structure. This data structure will support two operations:
Update(A) = Add an integer A to the collection.
Query(B) = Return the B'th smallest number from the collection.
For example, if the existing numbers in the collection are ( 1 , 4 , 3 , 7 , 5 ), then performing Query( 2 ) will return 3. If we perform Update( 2 ) on the existing collection, then Query( 6 ) will return 7.
You will have to perform 2 * N operations of this data structure. Each update operation will be immediately followed by a valid query operation. Please see the samples and explanation for further understanding.
The first line contains an integer N ( 1 ≤ N ≤ 105 ), the number of updates you have to perform for this dataset. You will also have to perform N query operations as well.
Next line contains N integers Ai ( 1 ≤ Ai ≤ 106 ), where each Ai indicates the number to be added for the i'th update operation.
Then follows another line with N numbers Bi ( 1 ≤ Bi ≤ i ). For each Bi, you will have to print the Bi'th integer in the collection after the i'th update operation.
For each query operation, print the answer on a line by itself.
6 1 4 3 7 5 2 1 2 2 4 3 6
1 4 3 7 4 7
7 1 4 3 10 15 20 25 1 2 2 4 5 6 7
1 4 3 10 15 20 25
In the first sample, the following are the first few instructions that are performed in order:
Update( 1 ) : Adds 1 to the collection, so it becomes ( 1 )
Query( 1 ) : Returns the first element of the collection, which is 1.
Update( 4 ) : Adds 4 to the collection, so it becomes ( 1 , 4 )
Query( 2 ) : Returns the second element of the collection, which is 4.
Update( 3 ) : Adds 3 to the collection, so it becomes ( 1 , 4 , 3 )
Query( 2 ) : Returns the second element of the collection, which is now 3.
Similarly, the remaining instructions will be performed in the following order: Update( 7 ), Query( 4 ), Update( 5 ), Query( 3 ), Update( 2 ) and Query( 6 ).