Limits 500ms, 512 MB

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 AA to the collection.

Query(B): Return the BB-th smallest number from the collection.

For example, if the existing numbers in the collection are (1,4,3,7,5)(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×N2 \times 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 NN (1N1051 ≤ N ≤ 10^5), the number of updates you have to perform for this dataset. You will also have to perform NN query operations as well.

Next line contains NN integers AiA_i (1Ai1061 ≤ A_i ≤ 10^6), where each AiA_i indicates the number to be added for the ii-th update operation.

Then follows another line with NN numbers BiB_i (1Bii1 ≤ B_i ≤ i). For each BiB_i, you will have to print the BiB_i-th integer in the collection after the ii-th update operation.


For each query operation, print the answer on a line by itself.


1 4 3 7 5 2
1 2 2 4 3 6


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)(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)(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)(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).

1 4 3 10 15 20 25
1 2 2 4 5 6 7


Login to submit.


63% Solution Ratio
Labib666Earliest, Feb '16
rkb_rdFastest, 0.0s
ShafinLightest, 2.0 MB
ashikurrahmanShortest, 443B
Toph uses cookies. By continuing you agree to our Cookie Policy.