Lift Problems

Several students wait for a lift on the ground floor of a large university building. Call that floor 0, and call the floors above it 1, 2, $\dots$, $n$ from the bottom up. The lift starts on floor 0 and only goes up.

Normally the lift stops at every floor where at least one student needs to get out. That annoys the students who want to get out higher up. If the lift skips a floor instead, it annoys the students who wanted to get out there.

Anger is counted like this. A student is annoyed on every floor where the lift stops while the lift has not yet reached the floor on which that student wants to get out. If the lift skips the floor a student wants, that student is annoyed on that floor and on every floor above it up to the floor just below the lift's next stop. At the next stop the student gets out and walks back down the stairs, and the anger ends there.

For example, a student wants to get out on floor 5 and the lift stops on floors 2, 7 and 10. That student is annoyed on floors 2, 5 and 6, so on three floors in total.

On entering the lift every student presses the button for the floor they want, even a button somebody else already pressed. The CPU that controls the lift therefore knows exactly how many students want to get out on each floor.

Write a program that decides which floors to stop at. The goal is to minimize the total amount of lift anger, that is, the number of floors on which every student is annoyed, added together over all students.

Ignore everyone who may want to enter the lift on a higher floor. Every student waiting on floor 0 has to be able to reach the floor they want, either by getting out there or by getting out at a stop above it and walking back down the stairs.

The first line holds the number of test cases. This value is positive and at most 100. Each test case then holds the following.

• One line with an integer $n$ ($1 \le n \le 1500$), the number of floors of the building, not counting floor 0.
• One line with $n$ space separated integers $s_1, s_2, \dots, s_n$ ($0 \le s_i \le 1500$), where $s_i$ is the number of students who want to get out on floor $i$.

For each test case print one line with a single integer, the smallest possible total amount of lift anger.