设一个包含不同正整数的集合。为了扩展集合以包含尽可能多的整数,Eri 可以从集合中选择两个整数 $$$x\neq y$$$,使得它们的平均值 $$$\frac{x+y}2$$$ 仍然是正整数并且不包含在集合中,并将其添加到集合中。整数 $$$x$$$ 和 $$$y$$$ 保留在集合中。
如果在元素排序后,任何一对相邻元素之间的差异为 $$$1$$$,则我们称该整数集为连续整数集。例如,集合 $$$\{2\}$$$、$$$\{2, 5, 4, 3\}$$$、$$$\{5, 6, 8, 7\}$$$ 是连续的,而 $$$\{2, 4, 5, 6\}$$$、$$$\{9, 7\}$$$ 则不是连续的。
Eri喜欢连续的组。假设有一个数组$$$b$$$,那么Eri将$$$b$$$中的所有元素放入集合中。如果经过上述有限次数的操作后,集合可以变得连续,则数组$$$b$$$将被称为辉煌的。
请注意,如果同一个整数在数组中多次出现,我们只将其放入集合中一次,因为集合始终包含不同的正整数。
Eri 有一个包含 $$$n$$$ 正整数的数组 $$$a$$$。请帮助他计算 $$$(l,r)$$$ 满足 $$$1 \leq l \leq r \leq n$$$ 的整数对的数量,并且子数组 $$$a_l, a_{l+1}, \ldots, a_r$$$ 非常出色。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 4 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$4 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——辉煌子数组的数量。
示例
输入 #1
6 2 2 2 6 1 3 6 10 15 21 5 6 30 18 36 9 1 1000000000 6 1 1 4 5 1 4 12 70 130 90 90 90 108 612 500 451 171 193 193
输出 #1
3 18 5 1 18 53
注意
在第一个测试用例中,数组 $$$a = [2, 2]$$$ 具有 $$$3$$$ 子数组:$$$[2]$$$、$$$[2]$$$ 和 $$$[2, 2]$$$。对于所有这些,该集合仅包含单个整数 $$$2$$$,因此它始终是连续的。所有这些子数组都很棒,所以答案是 $$$3$$$。
在第二个测试用例中,我们考虑子数组 $$$[3, 6, 10]$$$。我们可以进行如下操作:
$$$$$$\{3,6,10\} \xrightarrow{x=6,y=10} \{3,6,8,10\} \xrightarrow{x=6,y=8} \{3,6,7,8,10\} \xrightarrow{x=3,y=7} \{3,5,6,7,8,10\}$$$$$$ $$$$$$\xrightarrow{x=3,y=5} \{3,4,5,6,7,8,10\} \xrightarrow{x=8,y=10} \{3,4,5,6,7,8,9,10\}$$$$$$
$$$\{3,4,5,6,7,8,9,10\}$$$ 是连续的集合,因此子数组 $$$[3, 6, 10]$$$ 非常出色。