← 返回题目列表

Codeforces · 1848/B

B. 维卡和桥

中文机器翻译题面 查看原题

夏天,维卡喜欢参观她的乡间别墅。这里有放松的一切:舒适的秋千、自行车和河流。

河上有一座木桥,由 $$$n$$$ 木板组成。它很旧而且没有吸引力,所以维卡决定把它粉刷一下。在棚子里,他们刚刚发现了几罐$$$k$$$颜色的油漆。

在给每块木板涂上 $$$k$$$ 颜色之一后,维卡正准备去荡秋千,休息一下。然而她发现房子在河对岸,油漆还没有完全干,所以她还不能在桥上行走。

为了不破坏桥的外观,维卡决定仍然在桥上行走,但只踩相同颜色的木板。否则,她鞋底上的一小层油漆就会破坏另一种颜色的木板。维卡还剩下一点油漆,但只够重新粉刷桥的一块木板。

现在维卡站在第一块木板前面的地上。为了过桥,她会选择一些相同颜色的木板(重新粉刷后),其编号为 $$$1 \le i_1 < i_2 < \ldots < i_m \le n$$$ (木板从左到右编号为 $$$1$$$)。然后,由于 $$$m + 1$$$ 步中的每一步,维卡将必须穿过 $$$i_1 - 1, i_2 - i_1 - 1, i_3 - i_2 - 1, \ldots, i_m - i_{m-1} - 1, n - i_m$$$ 木板。

由于维卡害怕摔倒,所以她不想迈太远的步子。如果她能在过桥时将一块(或零块)木板重新涂上不同的颜色,请帮助她并告诉她一步中必须穿过的木板的最大数量。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) - 桥中木板的数量和不同颜色油漆的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$c_1, c_2, c_3, \dots, c_n$$$ ($$$1 \le c_i \le k$$$) — Vika 绘制桥板的颜色。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - Vika 在一步中必须跨过的木板的最小可能最大数量。

示例

输入 #1

5
5 2
1 1 2 1 1
7 3
1 2 3 3 3 2 1
6 6
1 2 3 4 5 6
8 4
1 2 3 4 2 3 1 4
3 1
1 1 1

输出 #1

0
1
2
2
0

注意

在第一个测试用例中,Vika 可以将中间的木板重新涂成 $$$1$$$ 颜色,并在不跨过任何木板的情况下走过桥。

在第二个测试用例中,Vika 可以将中间的木板重新涂成 $$$2$$$ 颜色,然后走过桥,每次只跨过一块木板。

在第三个测试用例中,Vika 可以将倒数第二块木板重新涂成 $$$2$$$ 颜色,然后走过桥,只踩在数字为 $$$2$$$ 和 $$$5$$$ 的木板上。那么 Vika 每次迈步时都必须跨过 $$$1$$$、$$$2$$$ 和 $$$1$$$ 木板,所以答案是 $$$2$$$。

在第四个测试用例中,Vika 可以简单地走过桥而无需重新粉刷,每次跨过两块木板,在颜色 $$$3$$$ 的木板上行走。

在第五个测试用例中,Vika 可以简单地走过桥,无需重新粉刷,也无需跨过任何木板。