AT_abc210_c [ABC210C] Colorful Candies

题目描述

有 $N$ 个糖果从左到右排成一列。
每个糖果的颜色是 $10^9$ 种颜色中的一种，分别为颜色 $1$、颜色 $2$、$\ldots$、颜色 $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$ 个糖果。

高桥君想要吃到尽可能多种不同颜色的糖果，
请输出他能获得的糖果中包含的颜色种类数的最大值。

输入格式

输入以如下格式从标准输入读入。

$N$ $K$ $c_1$ $c_2$ $\ldots$ $c_N$

输出格式

请输出高桥君能获得的糖果中包含的颜色种类数的最大值。

输入输出样例 #1

输入 #1

7 3
1 2 1 2 3 3 1

输出 #1

3

输入输出样例 #2

输入 #2

5 5
4 4 4 4 4

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

4

说明/提示

限制条件

• $1 \leq K \leq N \leq 3 \times 10^5$
• $1 \leq c_i \leq 10^9$
• 输入均为整数

样例解释 1

如果高桥君选择从左起第 $3$ 个到第 $5$ 个糖果，他能获得的糖果包含 $3$ 种颜色，这是最大值。

样例解释 2

高桥君可以获得所有排列好的糖果，但这些糖果只有 $1$ 种颜色。

由 ChatGPT 4.1 翻译