← 返回题目列表

Codeforces · 1736/C1

C1. 好的子数组(简单版)

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

这是这个问题的简单版本。在此版本中,我们没有查询。请注意,我们在此版本中有多个测试用例。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

如果对于所有 $$$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$$$。