There are $$$n$$$ horizontal rows of pins, numbered from $$$1$$$ to $$$n$$$ from top to bottom. Adjacent rows are one unit apart, and adjacent pins in the same row are one unit apart.
Row $$$i$$$ contains $$$a_i$$$ pins, where $$$a_1 \le a_2 \le \cdots \le a_n$$$. Its pins have coordinates $$$$$$ (0,i),(1,i),\ldots,(a_i-2,i),(a_i-1,i). $$$$$$ Thus, the leftmost pins of all rows lie on the same vertical line $$$x=0$$$, while longer rows extend farther to the right.
The following diagram shows the rows for $$$a=[1,2,4,4,7]$$$. The number written inside a pin is its horizontal coordinate. The orange square is one valid band of size $$$2$$$.
A rubber band of size $$$k$$$ is an axis-aligned square whose four vertices are pins at $$$$$$ (x,s),\quad(x+k-1,s),\quad(x,s+k-1),\quad(x+k-1,s+k-1) $$$$$$ for some integers $$$s$$$, $$$x$$$, and $$$k\ge1$$$. A band of size $$$1$$$ consists of a single pin. A pin is covered if it lies inside at least one band, and rubber bands may overlap.
Find the minimum number of rubber bands required to cover every pin.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of rows.
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the numbers of pins in the rows.
It is guaranteed that $$$a_1 \le a_2 \le \cdots \le a_n$$$ and that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, print one integer — the minimum number of rubber bands required to cover every pin.
6 1 4 2 2 2 3 1 3 3 4 3 4 5 5 3 2 8 8 5 1 2 4 6 8
4 1 3 4 5 7
In the first test case, there is only one row, so every pin requires its own size-$$$1$$$ band.
In the second test case, one size-$$$2$$$ band covers all four pins.
