题目描述

给出𝑁($1≤𝑁≤10^6$,𝑁是奇数)个初始值为0的整数，编号为1..𝑁。给出𝐾(1≤𝐾≤25,000)条格式为"𝐴 𝐵"的指令。意思是要让𝐴…𝐵中的整数加1。例如，𝐴=10,𝐵=13，那么要给10，11，12和13位置上的整数加1。 完成了所有指令后，计算𝑁个数字的中位数。

输入格式

第 1 行：两个空格分隔的整数，𝑁 𝐾。

第 2..1+K 行：每一行包含两个空格分隔的整数 𝐴, 𝐵 ($1 \leq 𝐴 \leq 𝐵\leq 𝑁$)的形式。

输出格式

第 1 行：𝑁 个数字中的中位数。

样例 #1

样例输入 #1

7 4
5 5
2 4
4 6
3 5

样例输出 #1

1

提示

输入解释：

有N=7个数字，K=4条指令。首先

指令是在第 5 - 5 位之间的数字加1 ... ...

输出解释：

完成后，各个位置上的数字为 0,1,2,3,3,1,0。中位数为 1，因为 1 是排序顺序中的中间元素0,0,1,1,2,3,3.