E-小红的中位数查询（easy）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

easy 版本中，所有的 $r - l + 1$ 都相等，而 hard 版本中没有此限制。通过 easy 版本可以获得 250 分，通过 hard 版本可以获得 50 分。

小红拿到了一个数组，她有若干次询问，每次询问一个区间，她希望你输出该区间的中位数是多少。

保证区间的元素数量为奇数。

在本难度中，保证所有区间的长度都相等。

区间中位数的定义：将区间所有元素从小到大排序后、最中间的那个数。例如[2,1,4]的中位数是2，[2,1,4,3,3]的中位数是3。

第一行输入两个正整数，代表数组大小、询问次数。
第二行输入个正整数，代表小红拿到的数组。
接下来的行，每行输入两个正整数，代表一次询问。



保证所有的为奇数，且都相等。

输出行，每行输出一个正整数，代表询问的结果。

示例1

复制

复制

2
3