Hello, and welcome to the warm-up session of the 10th China Collegiate Programming Contest Finals. Little Blue Fish has prepared some fresh and delicious stories for everyone and hopes to share them with you all. Of course, no matter how much Little Blue Fish wants to say, the first thing to do is to introduce himself. Therefore, Little Blue Fish wants to present his latest techniques at the Symposium on Theory of Loving (STOL).

Little Blue Fish wants to play a game with his idol. In this game, the idol has a sequence of integers $x_1, x_2, \dots, x_n$. Initially, all values of $x_i$ are $0$. The idol can perform the following operations any number of times:

• Choose an integer $k$ ($1 \le k \le n$). Then, for all $1 \le i \le k$, increase $x_i$ by $1$. The cost of this operation is $k$.
• Choose an integer $k$ ($1 \le k \le n$). Then, for all $n - k + 1 \le i \le n$, increase $x_i$ by $1$. The cost of this operation is $k$.

Little Blue Fish also has $n$ integers $y_1, y_2, \dots, y_n$. He hopes the idol will perform a series of operations such that $x_i \ge y_i$ holds for every $1 \le i \le n$.

This task is too simple for the idol. So he knows the minimum cost required to reach the goal. Therefore, your task is to write a program to calculate the minimum cost.

Input

The first line contains an integer $T$ ($1 \le T \le 10^5$), representing the number of test cases.

For each test case, the first line contains an integer $n$ ($1 \le n \le 10^6$).

The next line contains $n$ non-negative integers $y_1, y_2, \dots, y_n$ ($0 \le y_i \le 10^9$).

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

Output

For each test case, output a single integer representing the answer.

Examples

Input 1

3
5
1 1 1 1 1
10
0 0 0 0 1000000000 0 0 0 0 0
13
1 1 4 5 1 4 1 9 1 9 8 1 0

Output 1

5
5000000000
76