Swapped Rows and Zero‐Gravity Regions

We are given an n×n grid (with n even) that has exactly n key points such that each row and each column contains exactly one key point. The key point in row i is located at column p_i.

Define a zero–gravity region to be any sub–square of size \(\frac{n}{2}\times\frac{n}{2}\) formed by \(\frac{n}{2}\) consecutive rows and \(\frac{n}{2}\) consecutive columns that does not contain any key point.

For any swap of two rows \(i\) and \(j\) (\(1\le i<j\le n\)), let \(f(i,j)\) denote the number of zero–gravity regions (in the grid obtained by swapping the two rows) – note that the grid is never actually modified, and each swap is considered independently.

Your task is to compute the sum:

\[ \sum_{1\le i<j\le n}f(i,j). \]

Input format: The first line contains an even integer \(n\) (the size of the grid). The second line contains \(n\) integers \(p_1, p_2, \dots, p_n\); here \(p_i\) represents the column in which the key point of the \(i\)th row is located. It is guaranteed that \(p\) is a permutation of \(\{1,2,\ldots,n\}\) (i.e. every row and column has exactly one key point).

Note: A contiguous block of \(\frac{n}{2}\) rows (or columns) is defined by choosing an integer \(L\) with \(1 \le L \le n-\frac{n}{2}+1\) and forming the block \(\{L,L+1,\dots,L+\frac{n}{2}-1\}\).

inputFormat

The first line contains an even integer \(n\) (the number of rows/columns). The second line contains \(n\) space-separated integers \(p_1, p_2, \dots, p_n\), indicating the column positions of the key points in rows 1 through \(n\).

outputFormat

Output a single integer: the sum of \(f(i,j)\) over all pairs \(1 \le i < j \le n\).

sample

4
2 4 1 3

10