问题 K: 道士的干草堆

问题 K: 道士的干草堆

时间限制: 1 Sec  内存限制: 128 MB
提交: 25  解决: 7
[提交][状态][讨论版][命题人:]

题目描述

开始时，共有 N 个空干草堆，编号 1∼N。 北冥有鱼一共有K次询问，每次询问的格式为 A B，这意味着道士要在 A..B 范围内的每个干草堆的顶部添加一个新的干草捆。例如，如果道士听到 10 13，则他应在干草堆10,11,12,13 中各添加一个干草捆。 在道士完成了所有指令后，道士想知道 N 个干草堆的中值高度——也就是说，如果干草堆按照高度从小到大排列，位于中间的干草堆的高度，方便起见，N 一定是奇数，所以中间堆是唯一的。 请你帮助道士解决北冥有鱼的问题。

输入

第一行包含 N 和 K。

接下来 K 行，每行包含两个整数 A,B，用来描述一个指令。

输出

输出完成所有指令后，N 个干草堆的中值高度。

样例输入

7 4
5 5
2 4
4 6
3 5

样例输出

1

提示

1≤N≤1000000,

1≤K≤25000,

1≤A≤B≤N。

[提交][状态]