CF1973E Cat, Fox and Swaps

Fox 找到了一组数组 $p_1, p_2, \ldots, p_n$，这是一个长度为 $n$ 的排列，包含了 $1, 2, \ldots, n$ 这 $n$ 个数。她想将这些元素按升序排序。Cat 想帮助她——他可以交换数组中任意两个数 $x$ 和 $y$，但只有当 $l \leq x + y \leq r$ 时才允许交换（注意，这个限制是针对元素的值，而不是它们的位置）。他可以进行任意次数这样的交换。 他们还不知道 $l$ 和 $r$ 的具体数值，只知道 $1 \leq l \leq r \leq 2n$。 现在给定 $n$ 和数组 $p_1, p_2, \ldots, p_n$，请你计算有多少对整数对 $(l, r)$ 满足上述条件，使得在只能交换满足 $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 \leq t \leq 10^4$），表示测试数据组数。 每组测试数据包含两行。第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。 第二行包含 $n$ 个整数，表示数组 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$）。保证该数组是长度为 $n$ 的排列。 保证所有测试数据中 $n$ 的总和不超过 $10^5$。

对于每组测试数据，输出一个整数，表示满足条件的整数对 $(l, r)$ 的数量，其中 $1 \leq l \leq r \leq 2n$，并且在该限制下可以将数组排序。

在第一个样例中，我们需要能够交换 $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$，这样排列就被排序了。 由 ChatGPT 4.1 翻译