Add to Neighbour and Remove
Contest: Codeforces Round 690 (Div. 3)
Difficulty rating: 1400
Tags: greedy, math, number theory

Polycarp was given an array of $$$a[1 \dots n]$$$ of $$$n$$$ integers. He can perform the following operation with the array $$$a$$$ no more than $$$n$$$ times:

- Polycarp selects the index $$$i$$$ and adds the value $$$a_i$$$ to one of his choice of its neighbors. More formally, Polycarp adds the value of $$$a_i$$$ to $$$a_{i-1}$$$ or to $$$a_{i+1}$$$ (if such a neighbor does not exist, then it is impossible to add to it).
- After adding it, Polycarp removes the $$$i$$$-th element from the $$$a$$$ array. During this step the length of $$$a$$$ is decreased by $$$1$$$.

The two items above together denote one single operation.

For example, if Polycarp has an array $$$a = [3, 1, 6, 6, 2]$$$, then it can perform the following sequence of operations with it:

- Polycarp selects $$$i = 2$$$ and adds the value $$$a_i$$$ to $$$(i-1)$$$-th element: $$$a = [4, 6, 6, 2]$$$.
- Polycarp selects $$$i = 1$$$ and adds the value $$$a_i$$$ to $$$(i+1)$$$-th element: $$$a = [10, 6, 2]$$$.
- Polycarp selects $$$i = 3$$$ and adds the value $$$a_i$$$ to $$$(i-1)$$$-th element: $$$a = [10, 8]$$$.
- Polycarp selects $$$i = 2$$$ and adds the value $$$a_i$$$ to $$$(i-1)$$$-th element: $$$a = [18]$$$.

Note that Polycarp could stop performing operations at any time.

Polycarp wondered how many minimum operations he would need to perform to make all the elements of $$$a$$$ equal (i.e., he wants all $$$a_i$$$ are equal to each other).

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 3000$$$) — the number of test cases in the test. Then $$$t$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 3000$$$) — the length of the array. The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3000$$$.

Output format:
For each test case, output a single number — the minimum number of operations that Polycarp needs to perform so that all elements of the $$$a$$$ array are the same (equal).

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case of the example, the answer can be constructed like this (just one way among many other ways):

$$$[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,~add~to~right}$$$ $$$[16, 2]$$$ $$$\xrightarrow[]{i=2,~add~to~left}$$$ $$$[18]$$$. All elements of the array $$$[18]$$$ are the same.

In the second test case of the example, the answer can be constructed like this (just one way among other ways):

$$$[1, 2, 2, 1]$$$ $$$\xrightarrow[]{i=1,~add~to~right}$$$ $$$[3, 2, 1]$$$ $$$\xrightarrow[]{i=3,~add~to~left}$$$ $$$[3, 3]$$$. All elements of the array $$$[3, 3]$$$ are the same.

In the third test case of the example, Polycarp doesn't need to perform any operations since $$$[2, 2, 2]$$$ contains equal (same) elements only.

In the fourth test case of the example, the answer can be constructed like this (just one way among other ways):

$$$[6, 3, 2, 1]$$$ $$$\xrightarrow[]{i=3,~add~to~right}$$$ $$$[6, 3, 3]$$$ $$$\xrightarrow[]{i=3,~add~to~left}$$$ $$$[6, 6]$$$. All elements of the array $$$[6, 6]$$$ are the same.

Example input:
4
5
3 1 6 6 2
4
1 2 2 1
3
2 2 2
4
6 3 2 1

Example output:
4
2
0
2

Editorial:
Let $$$k$$$ — be the number of operations performed by Polycarp. Let's see how to check if $$$k$$$ is the answer.
Let's denote by $$$s$$$ the sum of numbers in the array $$$a$$$. Note that after each operation $$$s$$$ does not change. Since we know that after $$$k$$$ operations all elements must be the same and the sum of the numbers in the array does not change, then each of the remaining elements must be equal to $$$\frac{s}{n-k}$$$.
Let's check if it is possible to perform $$$k$$$ operations so that at the end all elements are equal to $$$\frac{s}{n-k}$$$. Note that the process described in the condition is equivalent to the following process:
• Choose a set of $$$n - k + 1$$$ indices $$$i_1, i_2, \dots, i_{n-k+1}$$$ ($$$1 = i_1 < i_2 < \dots < i_ {n - k} < i_ {n - k + 1} = n + 1$$$) — partitions;
• Create a new array $$$b$$$ of $$$n - k$$$ elements, where $$$$$$b_j = \sum\limits_{t=i_j}^{i_{j+1}-1} b_t$$$$$$
Then, to check if $$$k$$$ is the answer, it is necessary to split the $$$a$$$ array into $$$n - k$$$ subarrays, in which the sum of all elements is equal to $$$\frac{s}{n-k}$$$. Such a check can be implemented greedily in $$$\mathcal{O}(n)$$$. It is enough to go through the array from left to right and take an element into the current subarray until the sum in it exceeds $$$\frac{s}{n-k}$$$.
The resulting solution works in $$$\mathcal{O}(n \cdot \sigma(s))$$$ or $$$\mathcal{O}(n^2)$$$, where $$$\sigma(s)$$$ is the number of divisors $$$s$$$.