A - Determining Flat Intervals Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は、線路の保守点検を行っています。線路沿いには N 個の計測地点があり、地点 i（1 \leq i \leq N）における線路の高さは H_i です。

連続する K 個の地点の高さがすべて同じ値であるとき、その区間を平坦な区間と呼びます。より正確には、ある整数 l（1 \leq l \leq N - K + 1）について、H_l = H_{l+1} = \cdots = H_{l+K-1} が成り立つとき、地点 l, l+1, \ldots, l+K-1 からなる区間は平坦な区間です。

平坦な区間が一つでも存在するかどうかを判定してください。

制約

  • 1 \leq K \leq N \leq 2 \times 10^5
  • 0 \leq H_i \leq 10^9
  • 入力はすべて整数である。

入力

N K
H_1
H_2
\vdots
H_N
  • 1 行目には、計測地点の数 N と平坦な区間の長さ K がスペース区切りで与えられる。
  • 続く N 行のうち i 行目（1 \leq i \leq N）には、地点 i の高さ H_i が与えられる。

出力

平坦な区間が存在する場合は Yes を、存在しない場合は No を 1 行に出力せよ。

入力例 1

5 3
1
2
2
2
3

出力例 1

Yes

入力例 2

6 2
0
1
0
1
0
1

出力例 2

No

入力例 3

12 4
5
7
7
7
7
3
4
4
4
1
1
2

出力例 3

Yes

入力例 4

25 6
1
1
1
1
1
2
2
2
2
2
3
3
3
3
3
4
4
4
4
4
5
5
5
5
5

出力例 4

No

入力例 5

1 1
1000000000

出力例 5

Yes

Score : 233 pts

Problem Statement

Takahashi is performing maintenance inspections on a railway track. There are N measurement points along the track, and the height of the track at point i (1 \leq i \leq N) is H_i.

When K consecutive points all have the same height, that interval is called a flat interval. More precisely, for some integer l (1 \leq l \leq N - K + 1), if H_l = H_{l+1} = \cdots = H_{l+K-1} holds, then the interval consisting of points l, l+1, \ldots, l+K-1 is a flat interval.

Determine whether at least one flat interval exists.

Constraints

  • 1 \leq K \leq N \leq 2 \times 10^5
  • 0 \leq H_i \leq 10^9
  • All inputs are integers.

Input

N K
H_1
H_2
\vdots
H_N
  • The first line contains the number of measurement points N and the length of a flat interval K, separated by a space.
  • The i-th line (1 \leq i \leq N) of the following N lines contains the height H_i of point i.

Output

If a flat interval exists, print Yes; otherwise, print No on a single line.

Sample Input 1

5 3
1
2
2
2
3

Sample Output 1

Yes

Sample Input 2

6 2
0
1
0
1
0
1

Sample Output 2

No

Sample Input 3

12 4
5
7
7
7
7
3
4
4
4
1
1
2

Sample Output 3

Yes

Sample Input 4

25 6
1
1
1
1
1
2
2
2
2
2
3
3
3
3
3
4
4
4
4
4
5
5
5
5
5

Sample Output 4

No

Sample Input 5

1 1
1000000000

Sample Output 5

Yes