Submit solution

Points: 100
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Median

You are given an array a of n elements. Furthermore, there are q queries. Each query is of the form l r: What is the median element in the range [l,r]. 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

1 \le n,q \le 1e5 1 \le a[i] \le 1e4


Comments

There are no comments at the moment.