Colorful Candies

题目描述

有 $N$ 个糖果从左到右排成一行。
每个糖果的颜色是 $10^9$ 种颜色之一，称为 颜色 $1$、颜色 $2$、$\ldots$、颜色 $10^9$。
对于每个 $i = 1, 2, \ldots, N$，从左数第 $i$ 个糖果的颜色是 颜色 $c_i$。 在这一排中，高桥可以选择 $K$ 个连续的糖果并拿走它们。
也就是说，他可以选择一个整数 $i$ 满足 $1 \leq i \leq N-K+1$，并拿走从左数第 $i$ 个、第 $(i+1)$ 个、第 $(i+2)$ 个、$\ldots$、第 $(i+K-1)$ 个糖果。 高桥喜欢吃多色的糖果，所以他拿到的糖果中颜色越多，他就越高兴。
输出他可以得到的不同颜色数的最大可能值。

输入格式

输入按照以下格式从标准输入给出： $N$ $K$ $c_1$ $c_2$ $\ldots$ $c_N$

输出格式

打印高桥可以得到的不同颜色数的最大可能值。

7 3
1 2 1 2 3 3 1

3

5 5
4 4 4 4 4

1

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

4

提示

$1 \leq K \leq N \leq 3 \times 10^5$ $1 \leq c_i \leq 10^9$ 输入中的所有数值都是整数。如果高桥拿到第 $3$ 到第 $5$ 个糖果，它们将有 $3$ 种不同的颜色，这就是可能的最大值。
高桥也可以拿走所有这些糖果，但它们是单一颜色。

标签: AtCoder|abc210C

来源

AtCoder|abc210C