给定一个包含 $$$n$$$ 元素的数组 $$$a$$$。您可以对其应用以下操作任意多次:
- 从 $$$a$$$ 中选择一些大小为 $$$2k$$$ 的子数组,该子数组从位置 $$$l$$$ 开始($$$1\le l \le l+2\cdot{k}-1\le n$$$, $$$k \ge 1$$$),并且对于 $$$0$$$ 和 $$$k-1$$$ 之间的每个 $$$i$$$ (包含),将值 $$$a_{l+k+i}$$$ 分配给 $$$a_{l+i}$$$。
例如,如果 $$$a = [2, 1, 3, 4, 5, 3]$$$,则选择 $$$l = 1$$$ 和 $$$k = 2$$$,应用此操作,数组将变为 $$$a = [3, 4, 3, 4, 5, 3]$$$。
找到使数组的所有元素相等所需的最少操作数(可能为零)。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 数组的长度。
每个测试用例的第二行由 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) 组成 - 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
打印 $$$t$$$ 行,每行包含相应测试用例的答案 - 使用给定操作使数组中的所有元素相等所需的最小操作数。
示例
输入 #1
5 3 1 1 1 2 2 1 5 4 4 4 2 4 4 4 2 1 3 1 1
输出 #1
0 1 1 2 0
注意
在第一个测试中,所有元素都相等,因此不需要任何操作。
在第二个测试中,您可以应用 $$$k=1$$$ 和 $$$l=1$$$ 的一个运算,设置 $$$a_1 := a_2$$$,并且通过 $$$1$$$ 运算,数组变为 $$$[1, 1]$$$。
在第三个测试中,您可以应用 $$$k=1$$$ 和 $$$l=4$$$ 的一个操作,设置 $$$a_4 := a_5$$$,数组变为 $$$[4, 4, 4, 4, 4]$$$。
在第四个测试中,您可以应用 $$$k=1$$$ 和 $$$l=3$$$ 的操作,设置 $$$a_3 := a_4$$$,并且数组变为 $$$[4, 2, 3, 3]$$$,然后您可以应用 $$$k=2$$$ 和 $$$l=1$$$ 的另一操作,设置 $$$a_1 := a_3$$$, $$$a_2 := a_4$$$,数组变为 $$$[3, 3, 3, 3]$$$。
第五次测试中,只有一个元素,因此不需要进行任何操作。