给定一个长度为N的序列，有Q次询问，每次询问区间[L,R]的中位数。
数据保证序列中任意两个数不相同，且询问的所有区间长度为奇数。
第一行为N,Q。
第二行N个数表示序列。
接下来Q行，每行为L,R，表示一次询问。
输出Q行，对应每次询问的中位数。
5 3
1 4 8 16 2
1 5
3 5
3 3
4
8
8
40%的数据，N,Q ≤ 100；
70%的数据，N ≤ 100；
100%的数据，N ≤ 1000，Q ≤ 100000，序列中的元素为1到10^9之间的整数。
原文：http://www.cnblogs.com/Ackermann/p/5560008.html