P17753 「RSOI-3B」序列 / sequence

题目来源：【HT-126-Div.3】核桃 CSP-J 组模拟赛

小 R 有一个长度为 $n$ 的非负整数序列 $a$。 他会在 $[0,m]$ 内选择一个整数 $x$，并将 $\forall 1 \le i \le n$，$a_i \gets |a_i-x|$。 小 R 想知道有多少个合法的 $x$ 能使操作后的序列 $a$ 单调不降。

第一行，两个正整数 $n,m$，含义见题目描述。 第二行， $n$ 个非负整数 $a_1, a_2, ... , a_n$，表示序列 $a$。

一行一个正整数，表示答案。

**【数据范围】** **本题采用捆绑测试。** 对于所有测试数据，保证：$1\le n \le 10^5, 1\le m,a_i \le 10^9$。 | 子任务编号 | $n \le$ | $m \le$ | 分值 | |:-:|:-:|:-:|:-:| | 1 | $2$ | $10^9$ | $10$ | | 2 | $10^3$ | $10^3$ | $20$ | | 3 | $10^5$ | $10^6$ | $30$ | | 4 | $10^5$ | $10^9$ | $40$ |