Exam
Maria Petrovna is a lecturer at a university. Mid-semester, she administered a test with n tasks, arranged by increasing difficulty.
Maria Petrovna knows her students fall into three categories:
A Diligent student tackles the tasks in order of increasing difficulty, starting with the easiest, and continues without skipping until time runs out.
A Smart student approaches the tasks in order of decreasing difficulty, starting with the hardest, and also works without skipping until time is up.
A Bad student copies exactly one task from either a diligent or smart student. Importantly, two bad students cannot copy the same task from the same person.
Diligent and smart students always solve all tasks they attempt correctly.
Maria Petrovna dislikes cheating. If she discovers a task was copied, she discredits that task for both the copier and the original solver. After the test, she recorded how many students were credited with each task.
With exams approaching, Maria Petrovna wants to estimate the number of bad students in the group to plan retake sessions. Unfortunately, she lost the detailed records of credited tasks and only has a note of how many students were credited for each task.
She needs to determine the minimum number of bad students that could be in the group. Help her find this number.
Input
The input file contains multiple tests. The first line contains an integer T — the number of tests. Each test description follows.
Each test description consists of two lines. The first line contains an integer n — the number of tasks in the test. The second line lists a_i for each task, in order of increasing difficulty, representing the number of students credited with that task (0 ≤ a_i ≤ 10^9).
It is guaranteed that the total number of tasks across all tests does not exceed 10^5, and each test contains at least one task.
Output
For each test, output a single number — the minimum possible number of bad students.
Explanation of the examples
In the first test, Maria Petrovna might have had three diligent students, two solving two tasks each, and one solving just one, plus one smart student who solved the hardest task.
In the second test, Maria Petrovna might have had one smart student solving the last two tasks, four diligent students solving the first two tasks, and three bad students each copying the first task from a different diligent student. Consequently, out of seven solutions for the first task, six were annulled, leaving it credited only to the diligent student who wasn't copied from.