题目描述

现在有n(1 <= N <= 1,000,000, N 是奇数)个盒子，编号是1..n。

数学老师决定让他做一个难题，他让小x对这些盒子做k(1 <=k <= 25,000)次放糖块的操作（这得多少糖块呀）。

数学老师每次会给小x一个区间[a,b]，这时小x就会从编号是a的盒子到编号是b的盒子每个盒子都放一个糖块。

做完k次操作后，数学老师会问小x，在所有盒子的糖块个数中，这些糖块个数的中位数是多少。（最中间的值）。

因为n是奇数，所以这个答案肯定是唯一的。

输入格式

第一行：两个整数 n k。

接下来k行，每行一个区间 ai bi ，表示要放糖块的区间。

输出格式

一个整数，表示中位数的值。

样例数据

input

7 4

5 5

2 4

4 6

3 5

output

1

【样例解释】一共有7个盒子，4个操作，第一次在5号盒子里放1个，第二次在2 3 4号盒子里放。etc

放完糖块之后，盒子里的糖块依次是0,1,2,3,3,1,0.排过序后，数字1是中位数。

数据规模与约定

usaco 2011 stacking

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$