034 - There are few types of elements(★4) 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 4

問題文

長さ N の数列 a = (a_1, a_2, \ldots, a_N) と整数 K が与えられます。以下の条件を満たす 連続する 部分列のうち、最も長いものの長さを求めてください。

  • その部分列に含まれている要素は K 種類以下の値からなる。

制約

  • 1 \leq K \leq N \leq 100{,}000
  • 1 \leq a_i \leq 10^{9} (1 \leq i \leq N)
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

N K
a_1 a_2 \ldots a_N

出力

答えを出力してください。


入力例 1

5 1
1 2 3 4 5

出力例 1

1

K = 1 であって、数列内の要素の値が全て異なるので、答えは 1 です。


入力例 2

5 4
1 1 2 4 2

出力例 2

5

K = 4 であって、数列内の要素の値は 3 種類であるので、全ての要素を含んだ区間が条件を満たします。


入力例 3

10 2
1 2 3 4 4 3 2 1 2 3

出力例 3

4

条件を満たす区間のなかで長さが最大のものは、区間 [3, 6] です。


出典

「競プロ典型90問」34日目