Water Pump

$N$ walls stand in a line from west to east, numbered $1$ to $N$ starting at the west end. Wall $i$ is $h_i$ units tall. A wall lets no water through, its thickness is $0$, and every wall stands on flat ground at height $0$.

Wall $i$ and wall $i+1$ enclose a space of width $1$. That space is cell $i$, and the city has $N-1$ cells. One unit of water fills one cell to a depth of $1$, so a cell whose water level is $d$ holds $d$ units of water.

Heavy rain floods the city. Water crosses a wall once its level rises above the top of that wall, and water that crosses west of wall $1$ or east of wall $N$ leaves the city. After the rain stops, the water level in cell $i$ is

$\min\left(\max_{1 \le a \le i} h_a,\; \max_{i+1 \le b \le N} h_b\right)$

The governor picks one cell and puts a pump in cell $p$. The pump removes all water from cell $p$ and keeps removing whatever flows in. While the level in a cell is above the wall it shares with a neighboring cell, water crosses that wall into the neighbor, so water from distant cells can reach the pump. Pumping ends when no more water flows into cell $p$.

Pick $p$ so that the pump removes as much water as possible, and print how many units it removes. When $N = 1$ there is no cell, so the answer is $0$.

The first line has an integer $T$, the number of test cases. ($1 \le T \le 20$)

Each test case takes two lines. The first line has $N$, the number of walls. ($1 \le N \le 100{,}000$) The second line has the wall heights $h_1, h_2, \dots, h_N$ separated by spaces, where $h_i$ is the height of wall $i$. ($0 \le h_i \le 10{,}000$)

Print $T$ lines. Line $i$ holds the answer for the $i$-th test case, the largest number of water units a single pump can remove.