Fox 找到了一个数组 $$$p_1, p_2, \ldots, p_n$$$,它是数字 $$$1, 2, \ldots, n$$$ 的长度 $$$n^\dagger$$$ 的排列。她想按升序对元素进行排序。 Cat 想帮助她——他能够交换数组中的任意两个数字 $$$x$$$ 和 $$$y$$$,但前提是 $$$l \leq x + y \leq r$$$ (请注意,约束是施加在元素的值上,而不是它们的位置)。他可以多次进行此类交换。
他们还不知道数字 $$$l$$$、$$$r$$$,他们只知道 $$$1 \leq l \leq r \leq 2 \cdot n$$$ 是真的。
给定数字 $$$n$$$ 和数组 $$$p_1, p_2, \ldots, p_n$$$。确定有多少对 $$$(l, r)$$$ 满足条件,以便您可以对排列进行排序,如果您只能交换两个数字 $$$(x, y)$$$ 使得 $$$l \leq x + y \leq r$$$ (任意次数,可能是 $$$0$$$)。
$$$^\dagger$$$ 长度 $$$n$$$ 的排列是一个数组,由从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数组成,顺序任意。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的描述由两行组成。第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$)。
第二行包含 $$$n$$$ 整数:数组 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$)。保证该数组是长度为 $$$n$$$ 的排列。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印整数对 $$$(l, r)$$$ 的数量,使得 $$$1 \leq l \leq r \leq 2 \cdot n$$$ ,并且您可以在约束下对数组进行排序。
示例
输入 #1
7 2 2 1 3 3 1 2 4 3 2 1 4 5 5 3 1 2 4 5 1 2 3 4 5 6 3 2 1 5 4 6 6 1 3 2 4 5 6
输出 #1
6 11 23 29 55 46 58
注意
在第一个示例中,我们需要能够交换 $$$1$$$ 和 $$$2$$$,因此我们必须能够交换总和 $$$3$$$ 的数字。正好有 $$$6$$$ 对满足条件:$$$(1, 3), (2, 3), (3, 3), (1, 4), (2, 4)$$$ 和 $$$(3, 4)$$$,所以答案是 $$$6$$$。
在第二个示例中,满足条件的 $$$11$$$ 对是 $$$(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5)$$$ 和 $$$(4, 6)$$$。例如,如果我们选择 $$$(3, 4)$$$ 对,我们可以首先交换数字 $$$1$$$ 和 $$$2$$$,然后交换数字 $$$1$$$ 和 $$$3$$$,之后,排列就完成了。