题目描述

有 $n$ 座城市，从左到右编号依次为 $1,2,\dots,n$。

你需要按照如下规则占领城市：

• 时间 $1$ 的时候你占领了 $[1,n]$ 的任意一座城市，这座城市被称为起始城市。
• 时间 $2,\ldots,n$ 的时候你占领了一座与之前占领的城市相邻的城市。

如果对于每座城市 $i$，你都能不晚于时间 $a_i$ 占领这座城市，那你就赢了。

你肯定能发现能不能赢和起始城市有关，求在这 $n$ 座城市中哪些起始城市可以赢。

输入格式

输入包含多组测试数据。第一行包含测试数据的数量 $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$ 。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示有几座城市作为起始城市可以赢。

样例

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

3
0
1

说明/提示

样例解释

第1组测试数据：以第 $2$，$3$，$4$ 座城市作为起始城市可以赢。

第2组测试数据：没有任何一座城市作为起始城市可以赢。

第3组测试数据：以第 $5$ 座城市作为起始城市可以赢。