分数: 466 分
问题陈述
高桥是市政府的一名员工,负责管理某条道路上的路灯。
有 N 路灯沿着这条路排成一排,从左到右编号为路灯 1,路灯 2, \ldots,路灯 N。每盏路灯 i (1 \leq i \leq N) 有一个整数参数 S_i。该参数代表路灯的亮度,但对于故障路灯来说它可能为负值。
高桥需要暂时关闭路灯 T 以便更换灯泡。关闭时,路灯的亮度 T 被视为 0 无论其原始值如何 S_T.
根据本市安全标准,对于由以下部分组成的路段 K 连续路灯,将该路段内所有路灯中的最低亮度定义为该路段的“安全等级”。安全级别较低意味着该区域更暗且更危险。
虽然路灯 T 已关闭,高桥想要计算每个部分的安全级别 K 连续路灯,包括路灯 T,并确定其中的最大值。
更准确地说,考虑所有整数 l 满足以下条件:
- 1 \leq l 和 l + K - 1 \leq N
- l \leq T \leq l + K - 1 (该部分包括路灯 T)
对于每个 l,该部分的安全级别 [l, l+K-1] 定义如下。对于每个整数 i 满意 l \leq i \leq l+K-1,让
A_i = \begin{cases} 0 & (i = T) \\ S_i & (i \neq T) \end{cases}
然后其中的最小值 A_l, A_{l+1}, \ldots, A_{l+K-1} 是本节的安全级别。
计算所有的安全级别 l 满足条件,输出其中的最大值。
请注意,在给定的约束下,始终存在至少一个 l 满足条件。
约束
- 1 \leq N \leq 5 \times 10^5
- 1 \leq K \leq N
- 1 \leq T \leq N
- -10^9 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 所有输入值均为整数
输入
N K T S_1 S_2 \ldots S_N
- 第一行包含三个空格分隔的整数: N 代表路灯数量, K 代表一段的长度,以及 T 代表要关闭的路灯编号。
- 第二行包含空格分隔的整数 S_1, S_2, \ldots, S_N 代表每个路灯的亮度。
输出
在一行中输出所有部分中的最大安全级别 K 连续路灯,包括路灯 T,当路灯亮时 T 已关闭。
示例输入 1
5 3 3 2 -1 7 3 1
示例输出 1
0
示例输入 2
6 3 4 -5 3 2 10 -3 4
示例输出 2
0
示例输入 3
10 4 5 3 -2 5 1 8 -4 7 2 6 -1
示例输出 3
-2
示例输入 4
20 5 12 4 -3 7 2 -1 8 5 -6 3 9 1 100 -2 6 4 -7 3 8 2 -5
示例输出 4
-2
示例输入 5
1 1 1 1000000000
示例输出 5
0