Tea with Tangerines
Contest: Codeforces Round 824 (Div. 2)
Difficulty rating: 900
Tags: greedy, math

There are $$$n$$$ pieces of tangerine peel, the $$$i$$$-th of them has size $$$a_i$$$. In one step it is possible to divide one piece of size $$$x$$$ into two pieces of positive integer sizes $$$y$$$ and $$$z$$$ so that $$$y + z = x$$$.

You want that for each pair of pieces, their sizes differ strictly less than twice. In other words, there should not be two pieces of size $$$x$$$ and $$$y$$$, such that $$$2x \le y$$$. What is the minimum possible number of steps needed to satisfy the condition?

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains the integer $$$n$$$ ($$$1 \le n \le 100$$$).

Then one line follows, containing $$$n$$$ integers $$$a_1 \le a_2 \le \ldots \le a_n$$$ ($$$1 \le a_i \le 10^7$$$).

Output format:
For each test case, output a single line containing the minimum number of steps.

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

Note:
In the first test case, we initially have a piece of size $$$1$$$, so all final pieces must have size $$$1$$$. The total number of steps is: $$$0 + 1 + 2 + 3 + 4 = 10$$$.

In the second test case, we have just one piece, so we don't need to do anything, and the answer is $$$0$$$ steps.

In the third test case, one of the possible cut options is: $$$600,\ 900,\ (600 | 700),\ (1000 | 1000),\ (1000 | 1000 | 550)$$$. You can see this option in the picture below. The maximum piece has size $$$1000$$$, and it is less than $$$2$$$ times bigger than the minimum piece of size $$$550$$$. $$$4$$$ steps are done. We can show that it is the minimum possible number of steps.

Example input:
3
5
1 2 3 4 5
1
1033
5
600 900 1300 2000 2550

Example output:
10
0
4

Editorial:
Let's start with a simple solution.
Let's choose the minimum piece from $$$a$$$ and assume that it will remain the minimum until the end. As the array is sorted, let's define the minimum piece as $$$a_1$$$. It means that in the end, all pieces must be smaller or equal to $$$2 \cdot a_1 - 1$$$.
The lower bound of the answer for this solution is $$$\displaystyle{\sum\limits_{i=1}^{n}\left\lceil\frac{a_i}{2 * a_1 - 1}\right\rceil}$$$.
Let's show that this is achievable. For each piece, while its size greater than $$$2 \cdot a_1 - 1$$$, let's cut off a piece of size $$$2 \cdot a_1 - 1$$$. The only problem is that we could get a piece smaller than $$$a_1$$$ in the end. But it means that before the last cut we had a piece in the range $$$[2 \cdot a_1, 3 \cdot a_1 - 2]$$$. All pieces in this range can be easily cut into pieces of the right size in one move.
The only left question is why the minimum piece in the end should have size $$$a_1$$$. Actually, it shouldn't, but it gives the best answer anyway. As was described above, the lower bound of the solution with the minimal piece of size $$$x$$$ in the end is $$$\displaystyle{\sum\limits_{i=1}^{n}\left\lceil\frac{a_i}{2 * x - 1}\right\rceil}$$$. Having a minimal piece with a smaller size, we can't get anything better, because the lower bound will be equal or greater for all $$$x < a_1$$$.