Problem Description

The ground surface is uneven. Whenever a heavy rain comes, puddles will form on the ground.
Another heavy rain is coming soon, and you decide to modify the ground to reduce water accumulation.

The ground can be modeled as a positive integer sequence $a$ of length $n$, where $a_i$ represents the altitude at position $i$.
When it rains, water gathers in low places and cannot flow away to either side. For example, for the sequence $a = [3,1,5,1,2,3]$, the accumulated water after raining is shown in the figure below (there are $5$ cells of water):

Due to a lack of manpower, you only have time to change the altitude of exactly one position to any positive integer.

Ask: after the modification, what is the minimum number of water cells that can remain.

Input Format

The first line contains an integer $T$.
Then there are $T$ test cases, each consisting of two lines.
For each test case, the first line contains an integer $n$, the length of the sequence.
The second line contains $n$ integers, the sequence $a$.

Output Format

For each test case, output one integer per line: the minimum number of water cells.

3
6
3 2 1 1 2 3
6
1 1 4 5 1 4
6
1 9 1 9 8 10

2
0
1

Hint

Constraints.

For the first $5\%$ of the testdata, $1 \le n \le 5$.
For the first $20\%$ of the testdata, $1 \le \sum n \le 550$, $1 \le a_i \le 500$.
For the first $35\%$ of the testdata, $1 \le \sum n \le 5050$, $1 \le a_i \le 5000$.
For the first $50\%$ of the testdata, $1 \le \sum n \le 5050$, $1 \le a_i \le 10^9$.
For $100\%$ of the testdata, $1 \le n, \sum n \le 10^6$, $1 \le a_i \le 10^9$.

It is guaranteed that $1 \le T \le 10^4$.

Translated by ChatGPT 5