20pts

暴力。

60pts

首先我们发现对于任意一个插班生的座位$a_i$，听课认真度减少量$t_i$为$1,2,3,……,n-1$和$n-1,……,3,2,1$,这部分贡献可以直接算出来。

100pts

但是我们发现对于$a_j<t_j$,$a_j$会直接减到$0$贡献不足$t_j$,我们考虑预处理出不足的贡献$b_i$。 对于一位同学$j$，当插班生在$j+1$时，他会有$n-a_j-1$的不足的贡献，观察不难得出，当插班生在$j+1,j+2,……,k$时，同学$j$不足的贡献分别为$n-a_j-1,n-a_j-2,……,1$，同理，当插班生在$k,……,j-2,j-1$时，不足的贡献分别为$1,……,n-a_j-2,n-a_j-1$，是一个等差数列，于是考虑二阶差分。 对于差分数组$d$，我们处理一个$1,2,……,c-1,c,c-1,……,2,1$的数列，观察不难得出差分数组为$1,1,1,……,-1,-1,……,-1$，于是得到二维差分数组为$1,0,0,……0,-2,0,0,……,1$，即$d_(j-c+1)=1$,$d_(j+1)=-2$，$d_(j+c+1)=1$。我们对于每一个$j$统计同一个$d_j$数组，最后不忘减去自身被插班生占去的贡献单独讨论，最后两次前缀和合并数组。注意到左右端点容易有问题，我这里直接处理的，数组就爆了。 最后合并即$sum-左边等差数列-右边等差数列+不足的贡献$

#include<bits/stdc++.h>
#define int long long//小心见祖宗
using namespace std;
int n;
int a[600005];
int d[600020];
void work(int x,int val)
{
	d[x - (val - 1) + 200001] += 1,d[x + 1 + 200001] += -2,d[x + val + 1 + 200001] += 1;
}
signed main()
{
	cin >> n ;
	int sum = 0;
	for(int i =1;i <= n;i++)
	{
		cin >> a[i];
		sum += a[i];
	}
//	work(2,5);
	for(int i = 1;i <= n;i++)
		if(a[i] < n)
			work(i,n - a[i]);
	for(int i = 1;i <= 400003;i++)
		d[i] += d[i - 1];
	for(int i = 1;i <= 400003;i++)
		d[i] += d[i - 1];
	for(int i = 1;i <= n;i++)
		if(a[i] < n)
			d[i + 200001] -= n - a[i];
	for(int i = 1;i <= n;i++)
	{
		int sum1 = (i + n - 1) * (n - i) / 2,sum2 = (2 * n - i) * (i - 1) / 2;
		cout << sum - sum1 - sum2 + d[i + 200001] - a[i] << ' ' ;
	} 
	return 0;
}