Please read the new rule regarding the restriction on the use of AI tools. ×

B. Speedbreaker
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Djjaner - Speedbreaker
⠀

There are $$$n$$$ cities in a row, numbered $$$1, 2, \ldots, n$$$ left to right.

  • At time $$$1$$$, you conquer exactly one city, called the starting city.
  • At time $$$2, 3, \ldots, n$$$, you can choose a city adjacent to the ones conquered so far and conquer it.

You win if, for each $$$i$$$, you conquer city $$$i$$$ at a time no later than $$$a_i$$$. A winning strategy may or may not exist, also depending on the starting city. How many starting cities allow you to win?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of cities.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the deadlines for conquering the cities.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer: the number of starting cities that allow you to win.

Example
Input
3
6
6 3 3 3 5 5
6
5 6 4 1 4 5
9
8 6 4 2 1 3 5 7 9
Output
3
0
1
Note

In the first test case, cities $$$2$$$, $$$3$$$, and $$$4$$$ are good starting cities.

In the second test case, there are no good starting cities.

In the third test case, the only good starting city is city $$$5$$$.