/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 個のキャンディが左右一列に並んでいます。
それぞれのキャンディは、色 1、色 2、\ldots、色 10^9の、10^9 種類の色のうちいずれかの色をしています。
i = 1, 2, \ldots, N について、左から i 番目のキャンディの色は色 c_i です。
高橋君は並んでいるキャンディのうち、連続して並んだ K 個のキャンディをもらうことができます。
すなわち、1 \leq i \leq N-K+1 を満たす整数 i を選んで、
左から i 番目、i+1 番目、i+2 番目、\ldots、i+K-1 番目のキャンディをもらうことができます。
高橋君はいろいろな色のキャンディを食べたいので、
もらうキャンディに含まれる色の種類数が多いほどうれしい気持ちになります。
高橋君がもらうキャンディに含まれる色の種類数の最大値を出力してください。
制約
- 1 \leq K \leq N \leq 3 \times 10^5
- 1 \leq c_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K c_1 c_2 \ldots c_N
出力
高橋君がもらうキャンディに含まれる色の種類数の最大値を出力せよ。
入力例 1
7 3 1 2 1 2 3 3 1
出力例 1
3
高橋君が左から 3 番目から 5 番目のキャンディをもらうと、もらうキャンディに含まれる色は 3 種類になり、これが最大です。
入力例 2
5 5 4 4 4 4 4
出力例 2
1
高橋君は並んでいるすべてのキャンディをもらうことが出来ますが、もらうキャンディに含まれる色は 1 種類です。
入力例 3
10 6 304621362 506696497 304621362 506696497 834022578 304621362 414720753 304621362 304621362 414720753
出力例 3
4
Score : 300 points
Problem Statement
There are N candies arranged in a row from left to right.
Each of these candies has one color that is one of the 10^9 colors called Color 1, Color 2, \ldots, and Color 10^9.
For each i = 1, 2, \ldots, N, the color of the i-th candy from the left is Color c_i.
From this row, Takahashi can choose K consecutive candies and get them.
That is, he can choose an integer i such that 1 \leq i \leq N-K+1 and get the i-th, (i+1)-th, (i+2)-th, \ldots, (i+K-1)-th candy from the left.
Takahashi likes to eat colorful candies, so the more variety of colors his candies have, the happier he will be.
Print the maximum possible number of distinct colors in candies he gets.
Constraints
- 1 \leq K \leq N \leq 3 \times 10^5
- 1 \leq c_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K c_1 c_2 \ldots c_N
Output
Print the maximum possible number of distinct colors in candies Takahashi gets.
Sample Input 1
7 3 1 2 1 2 3 3 1
Sample Output 1
3
If Takahashi gets the 3-rd through 5-th candies, they will have 3 distinct colors, which is the maximum possible number.
Sample Input 2
5 5 4 4 4 4 4
Sample Output 2
1
Takahashi can get all of these candies, but they are in a single color.
Sample Input 3
10 6 304621362 506696497 304621362 506696497 834022578 304621362 414720753 304621362 304621362 414720753
Sample Output 3
4