P11158 [MX-X6-T4] Dream Gravity.

Original problem link: . --- > _空を仰げば$\\$ 青さが僕を$\\$ 飲み込んでしまう気がしてて$\\$ 無重力なら楽だろうか$\\$ 宇宙まで行けたら_ > > _—— [夢重力 - Nanatsukaze](https://music.163.com/#/song?id=2155399298)_ In the random motions of celestial bodies, how can we find a point with no gravity?

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: $$\sum_{1\leq i

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 one integer in a single line, representing the answer.

**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