Subarray Median Queries

Given an array of integers, this problem asks you to answer multiple queries to find the median of the subarray for each query. For each query, defined by indices (L) and (R) (1-indexed), you need to compute the median of the subarray (A[L...R]).

When the subarray has an odd length (n), the median is the element at the (\lfloor n/2 \rfloor + 1)-th position after sorting. When (n) is even, the median is defined as the lower of the two middle values, i.e. the element at position (n/2) after sorting.

Formally, if we let (S) be the sorted subarray of length (n), the median (M) is given by:
[ \text{Median}(S) = \begin{cases} S[\lfloor n/2 \rfloor] &\text{if } n \text{ is odd},\ S[\frac{n}{2}-1] &\text{if } n \text{ is even}. \end{cases} ]

inputFormat

The input is read from standard input (stdin). The first line contains an integer (N), the number of elements in the array. The second line contains (N) space-separated integers representing the array elements. The third line contains an integer (Q), the number of queries. Each of the next (Q) lines contains two integers (L) and (R) (1-indexed), representing the inclusive start and end indices of a subarray.

outputFormat

Print (Q) lines to standard output (stdout), where each line contains the median of the corresponding subarray as defined in the query.## sample

5
5 3 2 4 1
1
1 3

3