← 返回题目列表

Codeforces · 2101/D

D. 玛尼和段

中文机器翻译题面 查看原题

长度为 $$$|b|$$$ 的数组 $$$b$$$ 为 可爱 如果其最长递增子序列 (LIS) 的长度与其最长递减子序列 (LDS)$$$^{\text{*}}$$$ 的长度之和为 正是 比数组的长度多 1。更正式地说,如果 $$$\operatorname{LIS}(b) + \operatorname{LDS}(b) = |b| 则数组 $$$b$$$ 很可爱。 + 1$$$。

给你一个长度为 $$$n$$$$$^{\text{†}}$$$ 的排列 $$$a$$$。你的任务是计算排列 $$$a$$$ 中可爱的非空子数组 $$$^{\text{‡}}$$$ 的数量。

$$$^{\text{*}}$$$ 序列 $$$x$$$ 是序列 $$$y$$$ 的子序列,如果 $$$x$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$y$$$ 获得。

数组的最长递增(递减)子序列是其元素严格按递增(递减)顺序排序的最长子序列。

$$$^{\text{†}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

$$$^{\text{‡}}$$$数组 $$$x$$$ 是数组 $$$y$$$ 的子数组,如果 $$$x$$$ 可以通过删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素从 $$$y$$$ 获得。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 的可爱非空子数组的数量。

示例

输入
复制

5
3
3 1 2
5
2 3 4 5 1
4
3 4 1 2
7
1 2 3 4 5 6 7
10
7 8 2 4 5 10 1 3 6 9

输出
复制

6
15
9
28
36

注意

在第一个测试用例中,所有 $$$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$$$。