33OJ
登录 注册

#P17753. 「RSOI-3B」序列 / sequence

「RSOI-3B」序列 / sequence

背景

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

题目描述

小 R 有一个长度为 nn 的非负整数序列 aa。

他会在 [0,m][0,m] 内选择一个整数 xx,并将 ∀1≤i≤n\forall 1 \le i \le n,ai←∣ai−x∣a_i \gets |a_i-x|。

小 R 想知道有多少个合法的 xx 能使操作后的序列 aa 单调不降。

输入格式

第一行,两个正整数 n,mn,m,含义见题目描述。

第二行, nn 个非负整数 a1,a2,...,ana_1, a_2, ... , a_n,表示序列 aa。

输出格式

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

4 10
7 8 9 1
3

提示

【数据范围】

本题采用捆绑测试。

对于所有测试数据,保证:1≤n≤105,1≤m,ai≤1091\le n \le 10^5, 1\le m,a_i \le 10^9。

子任务编号 n≤n \le m≤m \le 分值
1 22 10910^9 1010
2 10310^3 2020
3 10510^5 10610^6 3030
4 10910^9 4040