Score : $300$ points

问题描述

有 $N$ 颗糖果从左到右排列成一行。
这些糖果中的每颗都有一个颜色，该颜色是从 Color $1$, Color $2$, $\ldots$, Color $10^9$ 这 $10^9$ 种颜色中的一种。
对于每个 $i = 1, 2, \ldots, N$，从左边数第 $i$ 颗糖果的颜色为 Color $c_i$。

从这一排糖果中，高桥可以选择连续的 $K$ 颗糖果并获取它们。
也就是说，他可以选择一个整数 $i$，满足 $1 \leq i \leq N-K+1$，然后获取从左边数第 $i$、$(i+1)$、$(i+2)$、$\ldots$、$(i+K-1)$ 颗糖果。

高桥喜欢吃多彩的糖果，因此他得到的糖果颜色种类越多，他就越开心。
请输出他可以获得的不同颜色糖果的最大数量。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 09:24:31