WhiteRaptor はついに TheRaptorLand で同類を見つけました！普通の WhiteRaptor とは異なり、TheRaptorLand には PinkRaptor、BlueRaptor、GreenRaptor といった様々な色のラプターがいます。
WhiteRaptor は TheRaptorLand にいる $n$ 匹のラプターを左から右へ $1$ から $n$ まで番号を振って一列に並べました。左から $i$ 番目のラプターの色は $c[i]$ です。彼は何匹かのラプターを選んで、地下室で永遠に一緒に過ごしたいと考えています。しかし、彼ができるのは、列の両端から $0$ 匹以上のラプターを取り除き、残ったすべてのラプターを保持することだけです。
残ったラプターが仲間外れにならないように、彼は「最も頻度の高いラプターの色の出現回数」と「最も頻度の低いラプターの色の出現回数」の差が $k$ を超えないようにしたいと考えています。ある色のラプターが全く残っていない場合、その色の出現回数は $0$ とみなすことに注意してください。
WhiteRaptor が保持できるラプターの最大数を求めてください。
入力
プログラムは標準入力から読み込む必要があります。 最初の行には、2 つの整数 $n$ と $k$ が含まれます。 2 行目には、$n$ 個の空白区切りの整数 $c[1], c[2], \dots, c[n]$ が含まれます。
出力
プログラムは標準出力に出力する必要があります。 保持できるラプターの最大数を表す整数を 1 つ出力してください。
制約
すべてのテストケースにおいて、入力は以下の範囲を満たします。
- $1 \le n \le 200\,000$
- $0 \le k \le 200\,000$
- すべての $1 \le i \le n$ に対して $1 \le c[i] \le 3$
プログラムは以下の制限を満たす入力インスタンスでテストされます。
| 小課題 | スコア | 追加の制約 |
|---|---|---|
| 0 | 0 | サンプルテストケース |
| 1 | 5 | $n \le 500$ |
| 2 | 9 | $n \le 2000$ |
| 3 | 11 | $c[i] \le 2$ |
| 4 | 15 | $k = 0$ |
| 5 | 16 | ある $1 \le j \le n$ が存在し、すべての $i \le j$ で $c[i] \neq 3$、かつすべての $i > j$ で $c[i] = 3$ |
| 6 | 20 | 3 匹以上の連続するラプターの列において、色 3 が最も少ない |
| 7 | 24 | 追加の制約なし |
入出力例
入力 1
11 2 2 2 1 2 1 3 2 1 2 1 1
出力 1
7
注記 1
ラプター 3 からラプター 9 までにおいて、$c[i] = 1, 2, 3$ であるラプターの数はそれぞれ 3, 3, 1 です。最大頻度と最小頻度の差は $k = 2$ を超えないため、このラプターの集合は WhiteRaptor の基準を満たします。
ラプター 3 からラプター 10 までの集合は無効な例です。なぜなら、$c[i] = 1$ であるラプターがもう 1 匹加わることで、最も多い色の頻度が 4 になるからです。その結果、最大頻度と最小頻度の差は 3 となり、$k = 2$ を超えてしまいます。
7 が WhiteRaptor の基準を満たしたまま保持できる最大のラプター数であることが示せます。
入力 2
6 2 2 1 3 3 3 3
出力 2
5
注記 2
WhiteRaptor はラプター 1 からラプター 5 までを選ぶべきです。
入力 3
7 0 1 2 1 2 1 2 1
出力 3
0
注記 3
ラプターのどの連続する部分列にも $c[i] = 3$ であるラプターが含まれないため、最も少ない色の頻度は常に 0 になります。これは、WhiteRaptor が空でないラプターの列を選択できないことを意味します。したがって、出力は 0 です。
このテストケースは、$j = n$ と置くことで（色 3 のラプターが現れない）、小課題 5 を満たすことに注意してください。