长度为 $$$|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$$$ 的可爱非空子数组的数量。
示例
输入复制
533 1 252 3 4 5 143 4 1 271 2 3 4 5 6 7107 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$$$。