紧急!请神犇们仔细读题!仔细读题!

描述

给定长度为N的序列a,和Q次询问,每次询问区间[L,R]的中位数是多少。

如果[L,R]的长度为奇数,则中位数为排序后处在中间位置的数,例如{-2, 16, 8, 4, 2}的中位数是4。

如果[L,R]的长度为偶数,则中位数为排序后处在中间位置的两个数的平均值,例如{16, 8, 4, 2}的中位数是6。如果平均之后出现了“.5”则一律舍去,例如{1, 2}的中位数是1。

输入格式

第一行为两个整数N,Q,以空格隔开。

接下来一行有N个整数,以空格隔开,代表序列a。

接下来Q行,每行两个整数L,R,以空格隔开,代表此次询问[L,R]区间。询问必定合法。

输出格式

输出Q行,每行对应这次询问的答案。

样例输入

5 2
-2 16 8 4 2
1 5
2 5

样例输出

4
6

数据范围与约定

对于100%的数据,N≤1000,序列a中的每个数都在-1000000000~1000000000以内。

其余特征见下表:

测试点序号 Q       其他特征
1, 2       ≤1000   无
3, 4       ≤100000 每次询问的[L,R]的长度均为奇数,序列a中的元素互不重复
5, 6       ≤100000 每次询问的[L,R]的长度均为奇数
7, 8       ≤100000 序列a中的元素互不重复
9, 10      ≤100000 无

样例解释

样例就是问题描述中的例子。

来源

原创