Median
You are given an array of elements. Furthermore, there are queries. Each query is of the form l r
: What is the median element in the range . In this case, we consider the median of an even length list the minimum of the two middle values.
Input Format
The first line is n q
, the number of elements and queries.
The next line contains the array a
. The next q
lines each contain two integers l r
, a query.
Sample Input
5 1
1 2 3 4 5
1 4
Sample Output
3
Constraints
Comments