CF2101D.Mani and Segments

一个长度为 $|b|$ 的数组 $b$ 被称为"可爱的"，当且仅当其最长递增子序列（LIS）的长度与最长递减子序列（LDS）的长度 $^{\text{∗}}$ 之和恰好比数组长度大 1。更正式地说，数组 $b$ 是可爱的当且仅当 $\operatorname{LIS}(b) + \operatorname{LDS}(b) = |b| + 1$。

给定一个长度为 $n$ 的排列 $a$ $^{\text{†}}$。你的任务是统计排列 $a$ 中所有非空子数组 $^{\text{‡}}$ 中满足可爱条件的数量。

$^{\text{∗}}$ 序列 $x$ 是序列 $y$ 的子序列，如果可以通过从 $y$ 中删除任意位置（可能为零或全部）的元素得到 $x$。

数组的最长递增（递减）子序列是指元素按严格递增（递减）顺序排列的最长子序列。

$^{\text{†}}$ 长度为 $n$ 的排列是由 $1$ 到 $n$ 的 $n$ 个不同整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（因为 $2$ 出现了两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中出现了 $4$）。

$^{\text{‡}}$ 数组 $x$ 是数组 $y$ 的子数组，如果可以通过从 $y$ 的开头和结尾删除若干（可能为零或全部）元素得到 $x$。

每个测试包含多个测试用例。第一行输入测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——排列 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）——排列 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出排列 $a$ 中满足可爱条件的非空子数组数量。

在第一个测试用例中，所有 6 个非空子数组都是可爱的：

• $[3]$：$\operatorname{LIS}([3]) + \operatorname{LDS}([3]) = 1 + 1 = 2$
• $[1]$：$\operatorname{LIS}([1]) + \operatorname{LDS}([1]) = 1 + 1 = 2$
• $[2]$：$\operatorname{LIS}([2]) + \operatorname{LDS}([2]) = 1 + 1 = 2$
• $[3, 1]$：$\operatorname{LIS}([3, 1]) + \operatorname{LDS}([3, 1]) = 1 + 2 = 3$
• $[1, 2]$：$\operatorname{LIS}([1, 2]) + \operatorname{LDS}([1, 2]) = 2 + 1 = 3$
• $[3, 1, 2]$：$\operatorname{LIS}([3, 1, 2]) + \operatorname{LDS}([3, 1, 2]) = 2 + 2 = 4$

在第二个测试用例中，一个可爱的子数组是 $[2, 3, 4, 5, 1]$，因为 $\operatorname{LIS}([2, 3, 4, 5, 1]) = 4$ 且 $\operatorname{LDS}([2, 3, 4, 5, 1]) = 2$，满足 $4 + 2 = 5 + 1$。

翻译由 DeepSeek V3 完成