The Dragon

The life of a flying dragon is hard. In a long, deep valley there is a row of pastures, numbered $1, 2, \dots, n$ from left to right. Pasture $i$ holds $a_i$ sheep.

The dragons' code of honor allows only one feast per day: a feast means choosing a single pasture and devouring every sheep on it.

The valley's slopes are so high that not even a dragon can cross them, so the dragon must fly along the valley and may choose which end to enter from each day — the left end or the right end. When it flies in to feast on pasture $x$, every pasture it passes over — pastures $1 \dots x-1$ if it entered from the left, or $x+1 \dots n$ if it entered from the right — has all of its sheep flee in panic, never to return.

On top of that, at the end of every day the flock on each pasture shrinks by $1$ because of wolves, disease, escapes, and rumors of flying dragons in the area.

The dragon cannot decide whether to raid the pastures one after another while watching the largest ones dwindle, or to start with the biggest and scatter many smaller flocks along the way. In the end it chose to solve the problem the modern way and ordered a program from you.

Find the maximum number of sheep the dragon can eat. If a pasture is eaten on day $t$ (the first feast is day $1$), the number of sheep gained is its original count minus $t-1$.

The first line contains the number of data sets $z$. Then $z$ data sets follow, one after another.

Each data set is a single line. It begins with the number of pastures $k$ ($1 \le k \le 10000$), followed by $k$ integers separated by spaces. Each integer is the number of sheep on the corresponding pasture and lies between $0$ and $100000$ inclusive.

For each data set, print on its own line the maximum number of sheep the dragon can eat.