\(\mathrm{O}(N^2)\) solution

Just as in Problem C, we assume that the number of operations is between \(0\) and \((N-1)\), inclusive. Let \(v_k\) be the sum of frustration of the \(N\) people resulting in performing the operation \(k\) times. Then the answer is the minimum value among \(v_0,v_1,\ldots\), and \(v_{N-1}\). Therefore, for each with the number of operations \(0,1,\ldots,N-1\), we can calculate \(v_0,v_1,\ldots,v_{N-1}\) as the sum of frustration of the \(N\) people, so that the answer is obtained in an \(\mathrm{O}(N^2)\) time. Now we will consider how to optimize it.

Using an advanced version of cumulative sums

The sum of frustration for all number of operations can be fast using cumulative sums, but with a little tweak.
Let \(t\) be the number of operations required to move Dish \(i\) in front Person \(i\). Then, the distribution of frustration is described as follows:

• The frustration that Person \(i\) gains is \(0\) as a result of performing operations \(t\) times, \(1\) for \((t+1) \bmod N\) times, \(2\) for \((t+2) \bmod N\) times, \(\ldots\), and \(\lfloor \frac{N}{2} \rfloor\) for \((t+\lfloor \frac{N}{2} \rfloor) \bmod N\) times.
• The frustration that Person \(i\) gains is \(1\) for \((t-1) bmod N\) times, \(2\) for \((t-2) \bmod N\) times, \(\ldots\), and \(\lceil \frac{N}{2} \rceil\) for \((t-\lceil \frac{N}{2} \rceil) \bmod N\) times.

Thus, the frustration that Person \(i\) gains when the operation is performed s\(x\) times can be expressed as a linear function of \(x\) between \(t\) and \(x\) for the former and between \(x\) and \(t\) for the latter, as long as it does not stride between \(N-1\) and \(0\). Specifically, for the former we have \(x-t\), and for the latter \(-x+t\).
For now, let us put aside the possibility of striding between \(N-1\) and \(0\) and first explain how to optimize it. Since the sum of multiple linear functions can be calculated by summing the coefficients independently for each degree, we may calculate cumulative sums for terms of first and zeroth order each, so that we can obtain a linear function to find the sum of frustration as a result of \(x\) operations in a total of \(O(N)\) time, and the sum itself can be found by assigning the values of \(x\) into the obtained expression.

Handling the issue striding between \(N-1\) and \(0\)

Now we will introduce two ways to handle the cases of striding between \(N-1\) and \(0\).

Approach 1: considering \(3\) linear functions

Suppose that the description of the frustration that Person \(i\) strides between \(N-1\) and \(0\) in the former case. Then, the description can be rewritten as follows:

• The frustration is \(0\) for \(t\) times, \(1\) for \((t+1) \bmod N\) times, \(2\) for \((t+2) \bmod N\) times, \(\ldots\), and \(N-1-t\) for \(N-1\) times.
• The frustration is \(N-t\) for \(0\) times, \(N+1-t\) for once, \(\ldots\), and \(N + ((t+\lfloor \frac{N}{2} \rfloor) \bmod N) -t\) for \((t+\lfloor \frac{N}{2} \rfloor) \bmod N\) times.
• The frustration is \(1\) for \((t-1) \bmod N\) times, \(2\) for \((t-2) \bmod N\) times, \(\ldots\), and \(\lceil \frac{N}{2} \rceil\) for \((t-\lceil \frac{N}{2} \rceil) \bmod N\) times.

Considering the linear function \(x+N-t\) corresponding to the second description, we can compute the cumulative sums in the same way.
We can handle it similarly if the latter case strides between \(N-1\) and \(0\).

Approach 2: extending the range from \(0\) to \(2N-1\)

We used to consider that \(x\) directly corresponds to the number of operations, so we repeatedly wrote \(\bmod\ N\) to make the number take the value between \(0\) and \(N-1\). However, it results in a bothersome situation where incrementing \(N-1\) yields \(0\). To cope with this, we want to assume that \(N-1\) plus \(1\) equals \(N\).
Specifically, we calculate cumulative sums when the range of \(x\) is extended between \(0\) and \(2N-1\), and use the sum of \(x=0\) and \(x=N\) for performing the operation \(0\) times, the sum of \(x=1\) and \(x=N+1\) for once, \(\ldots\), and that of \(x=N-1\) and \(x=2N-1\) for \(N-1\) times. As a result, we may identify \(x\)’s with the same remainder modulo \(N\), thus we can just adopt the linear function without considering \(x\) modulo \(N\).
The sample code adopts this approach.

Sample code

#include <bits/stdc++.h>
using namespace std;

int main() {
    
	int N;
	cin>>N;
	
	vector<int> p(N);
	
	for(int i=0;i<N;i++)cin>>p[i];
	
	vector<long long> iv(N*2),ix(N*2);
	
	for(int i=0;i<N;i++){
		int j = (p[i]-i+N)%N;
		iv[j] -= j;
		iv[j+N/2+1] += j;
		ix[j] += 1;
		ix[j+N/2+1] -= 1;
		iv[N+j-(N-1)/2] += N+j;
		iv[N+j] -= N+j;
		ix[N+j-(N-1)/2] -= 1;
		ix[N+j] += 1;
	}
	
	for(int i=0;i<N*2-1;i++){
		iv[i+1] += iv[i];
		ix[i+1] += ix[i];
	}
	
	long long ans = 1000000000000000000;
	for(int i=0;i<N;i++){
		ans = min(ans,iv[i] + ix[i]*i + iv[i+N] + ix[i+N]*(i+N));
	}
	
	cout<<ans<<endl;
	
	return 0;
}