E. Кот, Лиса и обмены
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лиса нашла массив $$$p_1, p_2, \ldots, p_n$$$, который является перестановкой длины $$$n^\dagger$$$ чисел $$$1, 2, \ldots, n$$$. Она хочет отсортировать элементы в порядке возрастания. Кот хочет помочь Лисе — он может поменять местами любые два числа $$$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$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$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$$$, и вы сможете отсортировать массив при данных ограничениях.

Пример
Входные данные
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
Выходные данные
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$$$, после чего перестановка будет отсортирована.