A. Dungeon videogame
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider a dungeon consisting of $$$n$$$ levels, numbered from $$$1$$$ to $$$n$$$. You are given an array $$$a = a_1, a_{2}, ..., a_{n}$$$, where each element $$$a_{i}$$$ represents the number of points that can be scored at level $$$i$$$.

Initially, your score is $$$0$$$.

You have two available operations at every level from $$$1$$$ to $$$n$$$ :

  • Solve Level : Solve the $$$i_{th}$$$ level, and add $$$a_{i}$$$ points to your score. It is important to note that $$$a_{i}$$$ can be negative.
  • Skip Segment : Skip a contiguous range of levels, from $$$i_{th}$$$ to $$$j_{th}$$$ level, where $$$i \le j \le n$$$, and lose $$$(j - i + 1)$$$ points which equals to the number of levels in the chosen segment.

Note that you are allowed to apply exactly one of the two options above at each level.

Find the maximum possible score you can obtain.

Input

In the first line of the input You'll be given $$$t$$$ the number of testcases.

In the first line of each next $$$t$$$ testcases You'll be given an integer $$$n$$$ which shows the number of levels.

In the second line of each testcase You'll be given an array of length $$$n$$$.

$$$1 \le t \le 10^4$$$.

$$$1 \le n \le 2 \cdot 10^5$$$.

$$$1 \le |a_i| \le 10^9$$$.

It is guaranteed that sum of $$$n$$$ overall testcases does not exceed $$$2 \cdot 10^5$$$.

Output

Print the maximum score you can achieve.

Example
Input
4
5
-1 -1 -1 2 -1
3
5 5 6
2
-1000000000 1
5
-2 -2 3 4 -1
Output
-2
16
0
4