logo AlgoBeat OnlineJudge
登录 注册

#216795. [蓝桥杯 2026 国 B] 灯带修补

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

小蓝有一条环形灯带。灯带上按顺时针方向依次有 颗灯珠,第 颗灯珠的亮度为

若两颗相邻灯珠的亮度差的绝对值大于 ,则称这对相邻灯珠是不稳定的。由于灯带是环形的,第 颗灯珠和第 颗灯珠也相邻。

小蓝可以先在任意两颗相邻灯珠之间选择一个切口,将环形灯带展开成一排。随后,他要在这排中选择一段连续灯珠进行展示。

如果选中的展示段包含 颗灯珠,则段内有 对相邻灯珠需要检查。小蓝最多可以修补其中 对不稳定的相邻灯珠。展示段合法当且仅当段内不稳定相邻对的数量不超过

请你计算,在可以自由选择切口和展示段的情况下,小蓝最多能展示多少颗连续灯珠。

输入格式

第一行包含三个整数 ,分别表示灯珠数量、最多可修补的不稳定相邻对数量、稳定亮度差阈值。

第二行包含 个整数 ,其中 表示第 颗灯珠的亮度。

输出格式

输出一行,包含一个整数,表示最多可以选出的连续灯珠数量。

样例

样例输入 1

6 1 3
4 6 10 13 30 31

样例输出 1

4

样例输入 2

5 0 2
1 10 20 30 40

样例输出 2

1

样例输入 3

4 3 0
5 100 5 100

样例输出 3

4

数据范围与提示

【样例说明 1】

可以切在第 颗和第 颗灯珠之间。展开后选择第 到第 颗灯珠,亮度依次为

这段中共有 对相邻灯珠: 稳定, 不稳定, 稳定。修补 这一对后,可以展示 颗连续灯珠。

任意展示 颗连续灯珠时,段内都会包含至少 对不稳定相邻灯珠,超过 ,因此答案为

【样例说明 2】

只要展示段长度至少为 ,段内就会出现不稳定相邻对。由于 ,不能修补任何不稳定相邻对,所以最多只能展示一颗灯珠。

【样例说明 3】

可以选择合适的切口后展示全部 颗灯珠。展开后段内只有 对相邻灯珠需要检查,它们都不稳定,但都可以被修补,因此答案为

【评测用例规模与约定】

对于 的评测用例,

对于 的评测用例,

对于所有评测用例,