CF2011F.Good Subarray

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

我们称一个数组为好数组，当且仅当它可以通过以下步骤获得：创建一个只包含任意单个整数的数组；然后执行以下操作若干次：从已存在的数组中选择一个元素（称为 $ 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$ 个元素到第 $1$ 个元素；
• 从第 $1$ 个元素到第 $2$ 个元素；
• 从第 $2$ 个元素到第 $2$ 个元素；
• 从第 $3$ 个元素到第 $3$ 个元素。

在第二个例子中，唯一不好的子段是从第 $3$ 个元素到第 $4$ 个元素的子段。

By wangboyue。