求hack

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+9;
int n,a[2*N],l[N],r[N],s[2*N],t,d[N];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],a[i+n]=a[i];
	for(int i=2;i<=2*n;i++){
		while(t&&a[s[t]]>a[i]) t--;
		if(i>n) l[i-n]=(s[t]?(i-s[t]-1)%n+1:n-1);
		s[++t]=i;
	}
	t=0;
	for(int i=2*n-1;i>=1;i--){
		while(t&&a[s[t]]>=a[i]) t--;
		if(i<=n) r[i]=(s[t]?(s[t]-i-1)%n+1:n);
		s[++t]=i;
	}
	for(int i=1;i<=n;i++){
		d[1]+=a[i];
		d[l[i]+1]-=a[i];
		d[r[i]+1]-=a[i];
		d[l[i]+r[i]+1]+=a[i];
	}
	for(int i=1;i<=n;i++) d[i]+=d[i-1];
	for(int i=1;i<=n;i++) d[i]+=d[i-1];
	for(int i=2;i<=n;i++) cout<<d[i]<<endl;
	cout<<d[n]<<endl;
	return 0;
}