물 펌프

도시에 벽 $N$개가 서쪽에서 동쪽으로 한 줄로 서 있다. 벽에는 서쪽부터 $1$번부터 $N$번까지 번호가 붙어 있고, $i$번 벽의 높이는 $h_i$이다. 벽은 물을 통과시키지 않고 두께는 $0$이며, 높이가 $0$인 평평한 땅 위에 서 있다.

$i$번 벽과 $i+1$번 벽 사이에는 폭이 $1$인 공간이 생긴다. 이 공간을 $i$번 칸이라고 부르며, 도시에는 칸이 $N-1$개 있다. 물 한 단위는 칸 하나를 깊이 $1$만큼 채우는 양이므로, 수위가 $d$인 칸에는 물이 $d$단위 들어 있다.

폭우가 내려 도시가 잠긴다. 물은 수위가 벽 꼭대기보다 높아지면 그 벽을 넘고, $1$번 벽의 서쪽이나 $N$번 벽의 동쪽으로 넘어간 물은 도시 밖으로 빠져나간다. 비가 그친 뒤 $i$번 칸의 수위는 다음과 같다.

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

시장은 칸 하나를 골라 $p$번 칸에 펌프를 놓는다. 펌프는 $p$번 칸의 물을 전부 퍼내고, 흘러드는 물도 계속 퍼낸다. 어떤 칸의 수위가 이웃 칸과의 사이에 있는 벽보다 높으면 물은 그 벽을 넘어 이웃 칸으로 흐르므로, 떨어져 있는 칸의 물도 펌프까지 올 수 있다. $p$번 칸으로 더 이상 물이 흘러들지 않으면 퍼내기가 끝난다.

퍼내는 물이 가장 많아지도록 $p$를 고르고, 그때 퍼내는 물의 단위 수를 출력하라. $N = 1$이면 칸이 없으므로 답은 $0$이다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 20$)

각 테스트 케이스는 두 줄이다. 첫 줄에 벽의 개수 $N$이 주어진다. ($1 \le N \le 100{,}000$) 둘째 줄에 벽의 높이 $h_1, h_2, \dots, h_N$이 공백으로 구분되어 주어진다. $h_i$는 $i$번 벽의 높이다. ($0 \le h_i \le 10{,}000$)

$T$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 테스트 케이스의 답, 즉 펌프 하나로 퍼낼 수 있는 물의 최대 단위 수를 출력한다.