← 返回题目列表

Codeforces · 2018/B

B. 减速机

中文机器翻译题面 查看原题

连续有 $$$n$$$ 个城市,从左到右编号为 $$$1、2、\ldots、n$$$。

- 在$$$1$$$时刻,你征服了一座城市,称为起始城市。
- 在时间$$$2, 3, \ldots, n$$$,你可以选择一个与迄今为止被征服的城市相邻的城市并征服它。

如果对于每个 $$$i$$$,您在不晚于 $$$a_i$$$ 的时间征服城市 $$$i$$$,您就获胜。获胜策略可能存在也可能不存在,这也取决于起始城市。有多少个起始城市能让你获胜?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 城市数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — 征服城市的最后期限。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数:允许您获胜的起始城市的数量。

示例

输入 #1

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

输出 #1

3
0
1

注意

在第一个测试用例中,城市 $$$2$$$、$$$3$$$ 和 $$$4$$$ 是很好的起始城市。

在第二个测试用例中,没有好的起始城市。

在第三个测试用例中,唯一好的起始城市是城市$$$5$$$。