girfriends-request-1

Ashima is moody, and like most girlfriend suffers from serious mood swings. Currently, looking at Pankaj's interest in numbers, she got interested in them too. To protect himself from serious emotional blackmail, he has given Ashima some numbers to play with. Ashima being a loving girlfriend that she is, is not satisfied with playing with the numbers alone and wants Pankaj to play with her too. 

She has written down the numbers in a line and is asking Pankaj to tell her the median from some starting position to another. Pankaj has answered some such queries of her, but being playful that she is, she wants to play more. Pankaj needs your help in answering her queries. 
Definition: The median of a sequence of numbers is the middle element of that sequence when the sequence is sorted. For even number of elements in the sequence, the first of the middle two elements is called the median.
Input

The first line of the input contains N, the number of integers Pankaj gave Ashima to play with.
Next N lines contains one integer each, one of the numbers of the number given by Pankaj.
Next line contains an integer Q, the number of queries asked by Ashima. Next Q lines contain a pair of space separated integers (i, j), implying that Ashima is interested in the median of numbers in the sequence from i^th position to the j^th position (both included, 1-based indexing, i ≤ j).

Output:
Q lines, each containing the median for that particular query.
Constraints
1 ≤ N ≤ 1414
1 ≤ Q ≤ N^2
Each of the numbers in the sequence given by Pankaj to Ashima will be positive and fit into an integer.

Note: Large I/O. Be careful with certain languages.

SAMPLE INPUT
5
1
2
3
4
5
10
1 1
1 2
1 3
1 4
1 5
2 2
2 4
3 3
4 4
5 5

SAMPLE OUTPUT
1
1
2
2
3
2
3
3
4
5

Source: hackerearth | Difficulty: HARD
Tags: Dynamic programming

Data structures


Solutions: