Go Back

##### Save Dexterâ€™s Laboratory (250)

Description

Dee Dee has caused some trouble to Dexter once again and now his whole lab is about to explode! To prevent this destruction, Dexter has to perform a simple task. He is given a sequence of N integers and a set of Q queries. In each query, he is given two integers i and j. For each query, he has to find the difference between the ith greatest integer and jth smallest integer in the given sequence.

However, Dexter is too busy for solving this problem, as he is fighting against his arch-enemy Mandark. Can you help Dexter to save his laboratory by finding the required difference in each query?

Input

The first line of the input consists of a single integer N denoting the number of integers in the sequence.

The second line of the input consists of N space-separated integers (The sequence) .

The third line of the input consists of a single integer Q denoting the number of queries.

Q lines follow:

Each of these lines consists of two space-separated integers i and j.

Output

Output Q lines.

Each of these lines should consist of a single integer : the answer to the corresponding query, which is the difference between the ith greatest integer and the jth smallest integer in the given sequence.

( ith greatest integer - jth smallest integer)

Constraints

1 <= N <= 100000

-100000 <= A(k) <= 100000 ( where A(k) is the kth element in the sequence. ( 1 <= k <= N ) )

1 <= Q <= 10000

1 <= i, j <= N

Example

Copy Input

**Input:**

5

4 10 -1 7 -3

2

2 3

4 5

**Output:**

3

-11

Explanation

Query 1:

2nd greatest integer => 7

3rd smallest integer => 4

Answer = 7 - 4 = 3

Query 2:

4th greatest integer => -1

5th smallest integer => 10

Answer = -1 - 10 = -11

Ratings will be changed within 48 hours after the contest ends.