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: This article

2. An \(\mathrm{O}(N + \log M)\) solution obtained by the characteristics of the operation: https://atcoder.jp/contests/arc176/editorial/9852

\(\sum_{i=1}^{N-1} |P_i - P_{i+1}|\) coincides with the sum of the following values over \(k=1,2,\dots,N-1\):

• The number of \(i\) such that \(1 \le i \le N-1\) and \(\min(P_i,P_{i+1}) \le k < \max(P_i,P_{i+1})\).

This means that we can obtain the answer to the original problem as follows: replace the values in \(P\) that are less than or equal to \(k\) with \(0\), and those greater than \(k\) with \(1\), perform the operations of the problem, calculate the sum of \(\sum_{i=1}^{N-1} |P_i - P_{i+1}|\), and add up those sums over all \(k(1 \le k \le N-1)\).

Now, let’s solve the problem where all elements of \(P\) are \(0\) or \(1\). Consider finding the number of sequences of operations for each \(i\) such that \(|P_i - P_{i+1}| = 1\) after the operations. This can be done by performing matrix exponentiation with three states representing that there are \(j(0 \le j \le 2)\) zeros among \(P_i\) and \(P_{i+1}\).

Performing the above for all \(i,k\) would result in a time complexity of \(\mathrm{O}(N^2 \log M)\), but by using cumulative sums or similar to calculate beforehand for each \(k\) the number of \(i\) such that the number of elements among \(P_i\) and \(P_{i+1}\) that are not greater than \(k\) in the initial state is \(j\), we can find the answer for each \(k\) in \(\mathrm{O}(\log M)\). Therefore, this problem can be solved in \(\mathrm{O}(N \log M)\).

Sample Implementation