这是这个问题的简单版本。在此版本中,我们没有查询。请注意,我们在此版本中有多个测试用例。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
如果对于所有 $$$i$$$,第 $$$i$$$ 个元素大于或等于 $$$i$$$,则长度为 $$$m$$$ 的数组 $$$b$$$ 是好的。换句话说,$$$b$$$ 是好的当且仅当 $$$b_i \geq i$$$ 对于所有 $$$i$$$ ($$$1 \leq i \leq m$$$)。
给定一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。求索引对 $$$(l, r)$$$ 的数量,其中 $$$1 \le l \le r \le n$$$,使得数组 $$$[a_l, a_{l+1}, \ldots, a_r]$$$ 是好的。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数$$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$),即数组$$$a$$$的长度。
每个测试用例的第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$),表示数组 $$$a$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印合适的索引对的数量。
示例
输入 #1
3 3 1 2 3 3 1 1 1 4 2 1 4 3
输出 #1
6 3 7
注意
在第一个测试用例中,$$$a$$$ 的所有子数组都很好,因此所有对都是合适的。
在第二个测试用例中,$$$(1, 1)$$$、$$$(2, 2)$$$ 和 $$$(3, 3)$$$ 对是合适的。例如,当 $$$(l, r) = (1, 2)$$$ 时,数组 $$$b=[1,1]$$$ 不好,因为 $$$b_2 < 2$$$。