← 返回题目列表

Codeforces · 2011/F

F. 好的子数组

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

给定一个整数数组 $$$a$$$,大小为 $$$n$$$。

如果可以使用以下算法获得一个数组,我们就称该数组为好数组:创建一个由任意单个整数组成的数组;然后执行任意次数的以下操作:从已经存在的数组中选择一个元素(我们称之为 $$$x$$$)并将 $$$x$$$、$$$(x-1)$$$ 或 $$$(x+1)$$$ 添加到数组末尾。

例如,数组 $$$[1, 2, 1]$$$、$$$[5]$$$ 和 $$$[3, 2, 1, 4]$$$ 是好的,而 $$$[2, 4]$$$ 和 $$$[3, 1, 2]$$$ 则不是。

你的任务是计算数组 $$$a$$$ 中好的连续子数组的数量。具有相同元素但位于数组 $$$a$$$ 不同位置的两个子数组被视为不同。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

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

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$ 1 \le a_i \le n)$$$。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 数组 $$$a$$$ 的良好连续子数组的数量。

示例

输入 #1

4
3
1 1 3
4
3 2 3 1
1
1
8
4 5 6 5 3 2 3 1

输出 #1

4
9
1
23

注意

在第一个示例中,以下四个子数组都很好:

- 从 $$$1$$$-st 到 $$$1$$$-st 元素;
- 从 $$$1$$$-st 到 $$$2$$$-nd 元素;
- 从 $$$2$$$-nd 到 $$$2$$$-nd 元素;
- 从 $$$3$$$-rd 到 $$$3$$$-rd 元素。

在第二个示例中,唯一不好的子数组是从 $$$3$$$-rd 元素到 $$$4$$$-th 元素的子数组。