102102: [AtCoder]ABC210 C - Colorful Candies

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

问题描述

有一排从左到右排列的$N$颗糖果。每颗糖果都有$10^9$种颜色中的一种，分别称为颜色$1$，颜色$2$，$\ldots$，颜色$10^9$。

对于$1, 2, \ldots, N$中的每个$i$，从左数第$i$颗糖果的颜色是颜色$c_i$。

Takahashi可以从这排糖果中选择$K$颗连续的糖果并得到它们。也就是说，他可以选择一个整数$i$，满足$1 \leq i \leq N-K+1$，并得到从左数第$i$颗到第$(i+K-1)$颗糖果。

Takahashi喜欢吃色彩丰富的糖果，所以他糖果的颜色种类越多，他就越开心。请输出他能得到的糖果中颜色种类的最大可能数量。

限制条件

• $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$

输出

输出Takahashi能得到的糖果中颜色种类的最大可能数量。

样例输入1

7 3
1 2 1 2 3 3 1

样例输出1

3

如果Takahashi选择第3颗到第5颗糖果，它们将有3种不同的颜色，这是可能的最大数量。

样例输入2

5 5
4 4 4 4 4

样例输出2

1

Takahashi可以得到所有这些糖果，但它们都是同一种颜色。

样例输入3

10 6
304621362 506696497 304621362 506696497 834022578 304621362 414720753 304621362 304621362 414720753

样例输出3

4