Subarray Median Queries

You are given an array A of 'N' integers and 'Q' queries.

For each query, you are given a start index L and an end index R (1-based), which define a subarray A[L...R].

Your task is to find the median of this subarray. The median of a subarray is defined as the element that would be at the middle position if the subarray were sorted in non-decreasing order.

If the subarray's length is len, the median is the element at index floor((len + 1) / 2) of the sorted subarray (1-based index).

Input Format:

The first line of input contains an integer 'N'.
The second line contains 'N' space-separated integers, representing the elements of array A.
The third line contains an integer 'Q', the number of queries.
The next 'Q' lines each contain two space-separated integers, L and R.

Output Format:

For each query, print the median of the subarray A[L...R] on a new line.

Note:

The problem uses 1-based indexing for L and R, which should be converted to 0-based for array access in most languages.

A naive solution would be to extract the subarray, sort it, and find the middle element for each query. This is too slow (O(Q * N log N)).

An optimized approach for the given constraints would typically involve a persistent segment tree or a similar advanced data structure that can answer order statistic queries on a range in O(log N) time. A simpler approach using a Fenwick tree (BIT) or segment tree on a sorted, coordinate-compressed version of the values is also possible.