给定一个整数数组 $$$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 元素的子数组。