Codeforces Round 975 (Div. 1) |
---|
Finished |
There are $$$n$$$ cities in a row, numbered $$$1, 2, \ldots, n$$$ left to right.
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?
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$$$.
For each test case, output a single integer: the number of starting cities that allow you to win.
366 3 3 3 5 565 6 4 1 4 598 6 4 2 1 3 5 7 9
3 0 1
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$$$.
Name |
---|