Hints: https://atcoder.jp/contests/arc176/editorial/9845

We have two solutions, so we will explain both.

1. An \(\mathrm{O}(N\log M)\) solution obtained by applying binarization: https://atcoder.jp/contests/arc176/editorial/9849

2. An \(\mathrm{O}(N + \log M)\) solution obtained by the characteristics of the operation: This article

For an integer pair \((i,j)\) such that \(1 \le i < j \le N\), focus on \(P_i\) and \(P_j\). Let \(a\) and \(b\) the indices of the destinations of \(P_i\) and \(P_j\) after the operation. Here, let \(x_k\) be the number of sequences of operations that ultimately result in the sets \(\{i,j\},\{a,b\}\) having \(k\) elements in common. This \(x_k\) can be found using matrix exponentiation or DP, and is determined independently of \((i,j)\). Moreover, there are equal numbers of sequences of operations that create two sets \(\{a_1,b_1\}\) and \(\{a_2,b_2\}\) with the same \(k\). (Note that we consider sets, so \(\{3,5\},\{5,3\}\) etc. are regarded as identical.)

Now, consider the following problem:

Find the number of sets $\{a,b\}$ that have $k$ elements in common with the set $\{i,j\}$ and satisfy $|a-b| = 1$.

Let \(y_k\) denote the answer to the above problem. Then, the number of sequences of operations where \(P_i\) and \(P_j\) are adjacent after the operation is \(\frac{y_0}{\frac{(N-2)(N-3)}{2}} x_0 + \frac{y_1}{2(N-2)} x_1 + \frac{y_2}{1} x_2\). (Here, we are using the fact that there are equal numbers of sequences of operations that create two sets \(\{a_1,b_1\}\) and \(\{a_2,b_2\}\) with the same \(k\).)

The values of \(y_0,y_1,y_2\) can be determined solely based on the following conditions:

• Does \(i = 1\) hold?
• Does \(i + 1 = j\) hold?
• Does \(j = N\) hold?

Therefore, by finding \(y_0,y_1,y_2\) for all integer pairs \((i,j)\) and taking the sum of \(|P_i - P_j| \times \left(\frac{y_0}{\frac{(N-2)(N-3)}{2}} x_0 + \frac{y_1}{2(N-2)} x_1 + \frac{y_2}{1} x_2 \right)\), this problem can be solved in \(\mathrm{O}(N^2)\).

Now, let’s speed up this algorithm. We only need to find the sum of \(|P_i - P_j|\) for each of the eight possible patterns regarding the above three conditions.

Since there are at most \(\mathrm{O}(N)\) pairs of \((i,j)\) that satisfy any one of the above three conditions, we can process each of them naively, and then subtract their sum from the whole to also process the pattern that does not satisfy any conditions. Therefore, this part can be solved in \(\mathrm{O}(N)\).

By combining the above, this problem can be solved in \(\mathrm{O}(N + \log M)\).

Sample Implementation