← 返回题目列表

Codeforces · 1462/D

D. 添加到邻居并删除

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

Polycarp 被赋予了 $$$a[1 \dots n]$$$ 的 $$$n$$$ 整数数组。他可以对数组 $$$a$$$ 执行以下操作不超过 $$$n$$$ 次:

- Polycarp 选择索引 $$$i$$$ 并将值 $$$a_i$$$ 添加到他选择的邻居之一。更正式地说,Polycarp 将 $$$a_i$$$ 的值添加到 $$$a_{i-1}$$$ 或 $$$a_{i+1}$$$ (如果这样的邻居不存在,则不可能添加到它)。
- 添加后,Polycarp 从 $$$a$$$ 数组中删除第 $$$i$$$ 个元素。在此步骤中,$$$a$$$ 的长度减少 $$$1$$$。

以上两项一起表示一项操作。

例如,如果 Polycarp 有一个数组 $$$a = [3, 1, 6, 6, 2]$$$,那么它可以用它执行以下操作序列:

- Polycarp 选择 $$$i = 2$$$ 并将值 $$$a_i$$$ 添加到 $$$(i-1)$$$ 第一个元素:$$$a = [4, 6, 6, 2]$$$。
- Polycarp 选择 $$$i = 1$$$ 并将值 $$$a_i$$$ 添加到 $$$(i+1)$$$ 第一个元素:$$$a = [10, 6, 2]$$$。
- Polycarp 选择 $$$i = 3$$$ 并将值 $$$a_i$$$ 添加到第 $$$(i-1)$$$ 个元素:$$$a = [10, 8]$$$。
- Polycarp 选择 $$$i = 2$$$ 并将值 $$$a_i$$$ 添加到第 $$$(i-1)$$$ 元素:$$$a = [18]$$$。

请注意,Polycarp 可以随时停止执行操作。

Polycarp 想知道他需要执行多少次最小操作才能使 $$$a$$$ 的所有元素相等(即,他希望所有 $$$a_i$$$ 彼此相等)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 3000$$$) — 测试中的测试用例数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 3000$$$) — 数组的长度。下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — 数组 $$$a$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3000$$$。

输出

对于每个测试用例,输出一个数字 - Polycarp 需要执行的最小操作数,以便 $$$a$$$ 数组的所有元素都相同(相等)。

示例

输入 #1

4
5
3 1 6 6 2
4
1 2 2 1
3
2 2 2
4
6 3 2 1

输出 #1

4
2
0
2

注意

在示例的第一个测试用例中,答案可以这样构造(只是许多其他方法中的一种方法):

$$$[3, 1, 6, 6, 2]$$$ $$$\xrightarrow[]{i=4,~add~to~left}$$$ $$$[3, 1, 12, 2]$$$ $$$\xrightarrow[]{i=2,~add~to~right}$$$ $$$[3, 13, 2]$$$ $$$\xrightarrow[]{i=1,~添加~到~右}$$$ $$$[16, 2]$$$ $$$\xrightarrow[]{i=2,~添加~到~左}$$$ $$$[18]$$$。数组 $$$[18]$$$ 的所有元素都相同。

在示例的第二个测试用例中,答案可以这样构造(只是其他方式中的一种方式):

$$$[1, 2, 2, 1]$$$ $$$\xrightarrow[]{i=1,~add~to~right}$$$ $$$[3, 2, 1]$$$ $$$\xrightarrow[]{i=3,~add~to~left}$$$ $$$[3, 3]$$$。数组 $$$[3, 3]$$$ 的所有元素都相同。

在示例的第三个测试用例中,Polycarp 不需要执行任何操作,因为 $$$[2, 2, 2]$$$ 仅包含相等(相同)的元素。

在示例的第四个测试用例中,答案可以这样构造(只是其他方式中的一种方式):

$$$[6, 3, 2, 1]$$$ $$$\xrightarrow[]{i=3,~add~to~right}$$$ $$$[6, 3, 3]$$$ $$$\xrightarrow[]{i=3,~add~to~left}$$$ $$$[6, 6]$$$。数组 $$$[6, 6]$$$ 的所有元素都相同。