E - Streetlight Inspection Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は市役所の職員で、ある通りの街灯の管理を担当しています。

この通りには N 本の街灯が一列に並んでおり、左から順に街灯 1, 街灯 2, \ldots, 街灯 N と番号がつけられています。街灯 i（1 \leq i \leq N）には整数値のパラメータ S_i が設定されています。このパラメータは街灯の明るさを表しますが、故障している街灯では負の値になることもあります。

高橋君は、街灯 T の電球を交換するため、一時的にその街灯を消灯する必要があります。消灯中は、街灯 T の明るさは元の値 S_T にかかわらず 0 として扱われます。

市の防犯基準では、連続する K 本の街灯からなる区間を考え、その区間内の全ての街灯の明るさの最小値を「その区間の安全度」と定めています。安全度が低いほど、その区間は暗く危険であることを意味します。

高橋君は、街灯 T を消灯している間に、街灯 T を含む連続する K 本の街灯からなる全ての区間について安全度を求め、その中での最大値を把握したいと考えています。

より厳密には、以下の条件を全て満たす整数 l を考えます：

  • 1 \leq l かつ l + K - 1 \leq N
  • l \leq T \leq l + K - 1（区間が街灯 T を含む）

各 l に対して、区間 [l, l+K-1] の安全度を次のように定めます。l \leq i \leq l+K-1 を満たす各整数 i について、

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 つ以上存在します。

制約

  • 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
  • 1 行目には、街灯の本数を表す整数 N、区間の長さを表す整数 K、消灯する街灯の番号を表す整数 T が、スペース区切りで与えられる。
  • 2 行目には、各街灯の明るさを表す整数 S_1, S_2, \ldots, S_N がスペース区切りで与えられる。

出力

街灯 T を消灯したとき、街灯 T を含む連続する K 本の街灯からなる全ての区間における安全度の最大値を 1 行で出力せよ。

入力例 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

Score : 466 pts

Problem Statement

Takahashi is a city hall employee responsible for managing the street lights on a certain road.

There are N street lights lined up in a row along this road, numbered from left to right as street light 1, street light 2, \ldots, street light N. Each street light i (1 \leq i \leq N) has an integer parameter S_i. This parameter represents the brightness of the street light, but it can be negative for malfunctioning street lights.

Takahashi needs to temporarily turn off street light T in order to replace its bulb. While it is turned off, the brightness of street light T is treated as 0 regardless of its original value S_T.

According to the city's safety standards, for a section consisting of K consecutive street lights, the minimum brightness among all street lights in that section is defined as the "safety level" of that section. A lower safety level means the section is darker and more dangerous.

While street light T is turned off, Takahashi wants to compute the safety level for every section of K consecutive street lights that includes street light T, and determine the maximum value among them.

More precisely, consider all integers l satisfying the following conditions:

  • 1 \leq l and l + K - 1 \leq N
  • l \leq T \leq l + K - 1 (the section includes street light T)

For each l, the safety level of the section [l, l+K-1] is defined as follows. For each integer i satisfying l \leq i \leq l+K-1, let

A_i = \begin{cases} 0 & (i = T) \\ S_i & (i \neq T) \end{cases}

Then the minimum value among A_l, A_{l+1}, \ldots, A_{l+K-1} is the safety level of this section.

Compute the safety level for all l satisfying the conditions, and output the maximum value among them.

Note that under the given constraints, there always exists at least one l satisfying the conditions.

Constraints

  • 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)
  • All input values are integers

Input

N K T
S_1 S_2 \ldots S_N
  • The first line contains three space-separated integers: N representing the number of street lights, K representing the length of a section, and T representing the number of the street light to be turned off.
  • The second line contains space-separated integers S_1, S_2, \ldots, S_N representing the brightness of each street light.

Output

Output in a single line the maximum safety level among all sections of K consecutive street lights that include street light T, when street light T is turned off.

Sample Input 1

5 3 3
2 -1 7 3 1

Sample Output 1

0

Sample Input 2

6 3 4
-5 3 2 10 -3 4

Sample Output 2

0

Sample Input 3

10 4 5
3 -2 5 1 8 -4 7 2 6 -1

Sample Output 3

-2

Sample Input 4

20 5 12
4 -3 7 2 -1 8 5 -6 3 9 1 100 -2 6 4 -7 3 8 2 -5

Sample Output 4

-2

Sample Input 5

1 1 1
1000000000

Sample Output 5

0