CF1462D Add to Neighbour and Remove

Polycarp 得到一个长度为 $n$ 的整数数组 $a[1 \dots 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$ 的所有元素都相等所需的最小操作次数。

在第一个样例中，答案可以这样构造（仅为众多方案中的一种）： $[3, 1, 6, 6, 2] \xrightarrow[]{i=4,~加到左边} [3, 1, 12, 2] \xrightarrow[]{i=2,~加到右边} [3, 13, 2] \xrightarrow[]{i=1,~加到右边} [16, 2] \xrightarrow[]{i=2,~加到左边} [18]$。数组 $[18]$ 的所有元素都相等。 在第二个样例中，答案可以这样构造（仅为众多方案中的一种）： $[1, 2, 2, 1] \xrightarrow[]{i=1,~加到右边} [3, 2, 1] \xrightarrow[]{i=3,~加到左边} [3, 3]$。数组 $[3, 3]$ 的所有元素都相等。 在第三个样例中，Polycarp 不需要进行任何操作，因为 $[2, 2, 2]$ 中所有元素本来就相等。 在第四个样例中，答案可以这样构造（仅为众多方案中的一种）： $[6, 3, 2, 1] \xrightarrow[]{i=3,~加到右边} [6, 3, 3] \xrightarrow[]{i=3,~加到左边} [6, 6]$。数组 $[6, 6]$ 的所有元素都相等。 由 ChatGPT 4.1 翻译