Лиса нашла массив \(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\)).
Выходные данные
Для каждого набора входных данных выведите количество пар целых чисел \((l, r)\), таких, что \(1 \leq l \leq r \leq 2 \cdot n\), и вы сможете отсортировать массив при данных ограничениях.
Примечание
В первом примере нам нужно иметь возможность поменять местами \(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\), после чего перестановка будет отсортирована.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
6
11
23
29
55
46
58
|