CF2006C Eri and Expanded Sets

有一个包含正整数的集合。为了将这个集合扩展的尽可能大，Eri可以在集合中选择两个整数 $x \neq y $ ，需要满足它们的平均数 $ \frac{x+y}2 $ 是一个不在集合中的正整数，然后把 $ \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 有一个序列 $ a $ 包含 $ n $ 个合法的数。请帮他算出整数数对 $ (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_i $ 。 保证 $Σn \leq 4 \cdot 10^5$ 。

对于每组测试数据，输出一行一个整数，表示“闪耀的”子序列的数量。

在第一组测试数据中，序列 $ 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]$ 是闪耀的。