附加文件

【问题描述】

给出一个序列 A[1], A[2], ……, A[N] ( N 为奇数 )，开始时所有元素均为 0。给出 K 个操作，每个操作包含两个整数 L, R，表示给 A[L], A[L+1], ……, A[R] 均增加 1。

问：所有操作完成后，该序列的中位数是多少？

【输入】

第一行：两个正整数 N, K

接下来 K 行：每行两个整数 L, R, 表示一个操作。

【输出】

一个整数，表示答案。

【输入样例】

7 4
5 5
2 4
4 6
3 5

【输出样例】

1

【样例说明】

操作完后序列为：0,1,2,3,3,1,0。排序后为： 0,0,1,1,2,3,3。故中位数是 1。

【数据范围】

1 ≤ N ≤ 1,000,000 数据保证 N 是奇数

1 ≤ K ≤ 25,000

1 ≤ L ≤ R ≤ N