Background

Original problem link: https://oier.team/problems/X6E.

空を仰げば$\\$ 青さが僕を$\\$ 飲み込んでしまう気がしてて$\\$ 無重力なら楽だろうか$\\$ 宇宙まで行けたら

—— 夢重力 - Nanatsukaze

In the random motions of celestial bodies, how can we find a point with no gravity?

Problem Description

You are given an $n \times n$ grid with $n$ key points. It is guaranteed that each row and each column contains exactly one key point. It is also guaranteed that $n$ is even.

We define a zero-gravity region in the grid as a sub-square of size $\dfrac{n}{2} \times \dfrac{n}{2}$ formed by $\dfrac{n}{2}$ consecutive rows and $\dfrac{n}{2}$ consecutive columns, such that it contains no key points.

Let $f(i,j)$ be the number of different zero-gravity regions after swapping row $i$ and row $j$ of the grid. For all possible swaps, compute the sum of $f(i,j)$, i.e., you need to compute:

Note that computing $f$ does not actually perform the swap on the grid, and the grid will not be modified throughout the process.

Input Format

The first line contains an integer $n$. It is guaranteed that $n$ is even.

The next line contains $n$ space-separated integers $p_1, p_2, \dots, p_n$, meaning the $n$ key points are located at $(1,p_1),(2,p_2),\dots,(n,p_n)$. It is guaranteed that $p$ is a permutation.

Output Format

Output one integer in a single line, representing the answer.

4
1 2 3 4

8

10
9 8 1 10 7 2 4 3 6 5

27

Hint

Sample Explanation #1.

In the figure above, the top-left corresponds to the original grid. The gray parts indicate key points.

The following $6$ grids correspond to all possible swaps (in order: swapping $(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)$). The existing zero-gravity regions are marked in red and blue (purple indicates the intersection of two zero-gravity regions). It is easy to see that the answer is $2+2+0+0+2+2=8$.

Constraints.

For all testdata, it is guaranteed that $2\leq n\leq 2\times 10^5$ and $n$ is even, and $p$ is a permutation.

Bundled test, with a total of 4 subtasks. The limits are:

• Subtask 1 (12 pts): $n\leq 10$.
• Subtask 2 (19 pts): $n\leq 200$.
• Subtask 3 (34 pts): $n\leq 2000$.
• Subtask 4 (35 pts): no additional constraints.

Translated by ChatGPT 5