题目描述

为了弥补最近的一系列恶作剧，奶牛贝西答应帮农夫约翰叠 N 堆干草（N 为奇数）。
初始时，第 1…N 号堆都是空的。
接着，约翰会发出 K 条指令，每条指令形如 A B，表示：

在编号 A…B 的每一堆顶部都再放 1 捆干草。

全部指令执行完后，约翰想知道 所有堆高度的中位数。
（因为 N 为奇数，排序后直接取第 (N+1)/2 个即可。）

输入格式

• 第 1 行：两个空格分隔的整数 N K（1 ≤ N ≤ 1 000 000，1 ≤ K ≤ 25 000，N 为奇数）。
• 第 2…K+1 行：每行两个空格分隔的整数 A B（1 ≤ A ≤ B ≤ N），表示本次指令要加草的堆区间。

输出格式

• 第 1 行：一个整数，表示最终所有堆高度的中位数。

样例

样例输入

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 ≤ A ≤ B ≤ N
• 区间加 1 可用 差分数组 或 线段树 优化到 O(K + N)。