First of all, consider the minimum number of operations required to make an integer sequence \(A=(A_1,A_2,\ldots,A_N)\) equal another given sequence \(B=(B_1,B_2,\ldots,B_N)\).

Firstly, if the sums are different, i.e. if \(\displaystyle\sum_{i=1}^N A_i \neq \sum_{i=1}^N B_i\), then you cannot make \(A\) equal \(B\), because the operation in the problem statement does not change the sum.
On the other hand, if the sums are equal, one can always make \(A\) equal \(B\) with \(\left( \displaystyle\sum_{i=1}^{N-1}\lvert S_i-T_i\rvert \right)\) operations, where \(S_i=\displaystyle\sum_{k=1}^i X_k\) and \(T_i=\displaystyle\sum_{k=1}^i Y_k\) for all \(0\leq i\leq N\). This is because the operation in the problem statement effectively modifies \(S_i\) as follows:

• choose an integer \(i\) such that \(1\leq i\leq N-1\) to decrease \(S_i\);
• choose an integer \(i\) such that \(1\leq i\leq N-1\) to increase \(S_i\),

and there are one-by-one correspondences between “\((S_0=0,S_1,S_2,\ldots,S_{N-1},S_N)\) and \((A_1,A_2,\ldots,A_N)\)” and “\((T_0=0,T_1,T_2,\ldots,T_{N-1},T_N)\) and \((B_1,B_2,\ldots,B_N)\)”. (Note that \(S_N=T_N\) naturally holds because they have the same sum.)

Next, consider the candidates of the final conforming \(B=(B_1,B_2,\ldots,B_N)\) from the given \(A\). First, by the conditions in the problem statement, there must exist an integer \(x\) such that each \(B_i\) is either \(x\) or \(x+1\). Moreover, by the condition of the sequence that can be obtained from \(A\) by the operation, \(\displaystyle\sum_{i=1}^N B_i=S_N\) should hold.

Then, if \(B_i\leq \frac{S_N}{N}-1\) for some \(i\), then \(\displaystyle\sum_{i=1}^N B_i\leq (\frac{S_N}{N}-1)+(N-1)\times\frac{S_N}{N}=S_N-1\), so it is inappropriate. Similarly, if \(B_i\geq \frac{S_N}{N}+1\) for some \(i\), then \(\displaystyle\sum_{i=1}^N B_i\geq (\frac{S_N}{N}+1)+(N-1)\times\frac{S_N}{N}=S_N+1\), so it is also inappropriate. Therefore, each \(B_i\) should be an integer such that \(\frac{S_N}{N}-1<B_i<\frac{S_N}{N}+1\).

• If \(S_N\) is not a multiple of \(N\)

\(B_i=\lfloor \frac{S_N}{N}\rfloor\) or \(\lfloor\frac{S_N}{N}\rfloor+1\) should hold for all \(i\) (where \(\lfloor\frac{S_N}{N}\rfloor\) denotes the maximum integer no greater than \(\lfloor\frac{S_N}{N}\rfloor\)). Among integers \(i\) such that \(1\leq i\leq N\), if \(k\) integers of them satisfy \(B_i=\lfloor\frac{S_N}{N}\rfloor+1\) and \((N-k)\) of them satisfy \(B_i=\lfloor\frac{S_N}{N}\rfloor\), then \(S_N=\displaystyle\sum_{i=1}^NB_i=N\cdot\left\lfloor\frac{S_N}{N}\right\rfloor+k\equiv k\pmod{N}\). Thus, if we represent \(S_N=N\cdot \lfloor\frac{S_N}{N}\rfloor+r\) (\(1\leq r\leq N-1)\), then \(B\) must be composed of \(r\) copies of \(\lfloor\frac{S_N}{N}\rfloor+1\) and \((N-r)\) copies of \(\lfloor\frac{S_N}{N}\rfloor\). Conversely, if it is composed of them, then the condition in the problem statement is satisfied, and also \(A\) can be changed into \(B\).

• If \(S_N\) is a multiple of \(N\)

\(B_i=\frac{S_N}{N}\) must hold for all \(i\), and it indeed satisfies the condition. This can be considered as the \(r=0\) case of the non-multiple-of-\(N\) \(S_N\) above.

The minimum value of \(\displaystyle\sum_{i=1}^{N-1}\lvert S_i-T_i\rvert\) over all candidates of \(B\) can be found with a Dynamic Programming (DP).

Let \(dp[i][j]\) \((0\leq i\leq N, 0\leq j\leq \min(i,r))\) be the minimum value of \(\displaystyle\sum_{k=1}^{i}\lvert S_k-T_k\rvert\) such that, among \(B_1,B_2,\ldots\), and \(B_i\), \(j\) elements \(B_k\) satisfy \(B_k=\lfloor\frac{S_N}{N}\rfloor+1\); then \(dp[0][0]=0\) and

\[ dp[i][j]=\min(dp[i-1][j-1],dp[i-1][j])+\left\lvert i\cdot\left\lfloor\frac{S_N}{N}\right\rfloor +j-S_i\right \rvert. \]

(Here, \(dp[i-1][j-1]=+\infty\) if \(j=0\) and \(dp[i-1][j]=+\infty\) if \(j=i\).) The answer is the value \(dp[N][r]\). Since each \(dp[i][j]\) can be found from \(dp[i-1][j-1]\) and \(dp[i-1][j]\) in an \(O(1)\) time, the overall complexity is \(O(N^2)\); since the constraints guarantee that \(N\leq 5000\), the answer can be found fast enough.

Sample code in C++:

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

int main(void){
	int n,r;
	long long d;
	long long a[5000],dp[5000],dp2[5000];

	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];

	for(int i=0;i<n-1;i++)a[i+1]+=a[i];
	if(a[n-1]>=0){
		d=a[n-1]/n;
		r=a[n-1]%n;
	}
	else{
		r=(n-(-a[n-1])%n)%n;
		d=(a[n-1]-r)/n;
	}

	dp[0]=0;
	for(int i=0;i<n;i++){
		dp2[0]=dp[0]+abs(d*(i+1)-a[i]);
		for(int j=0;j<min(r,i);j++)dp2[j+1]=min(dp[j],dp[j+1])+abs(d*(i+1)+j+1-a[i]);
		if(i+1<=r)dp2[i+1]=dp[i]+abs((d+1)*(i+1)-a[i]);
		for(int j=0;j<=min(r,i+1);j++)dp[j]=dp2[j];
	}

	cout<<dp[r]<<endl;
	return 0;
}