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

int main()
{
    ll N;
    cin>>N;
    vector<ll>arr(N,0);
    ll maxi=0;
    for(ll i=0;i<N;i++)
    {
    	cin>>arr[i];
    	maxi=max(maxi,arr[i]);
	}
	
	
    ll i=0;
    ll j=N-1;
    ll ans=0;
    
    
    
    vector<ll>mapper(maxi+100,0);
    for(ll i=0;i<=maxi+1;i++)
    {
    	mapper[i]=i;
	}
	vector<ll>sizes(maxi+100,1);
	
	
    while(i<j)
    {
    	if(arr[i]!=arr[j])
    	{
    	  ll i1=arr[i];
		  ll i2=arr[j];
		  while(i1!=mapper[i1])
		  {
		  	i1=mapper[i1];
		  }
		  while(i2!=mapper[i2])
		  {
		  	i2=mapper[i2];
		  }	
		  	
		  if(i1!=i2)
		  {
		  	ans++;
		  	if(sizes[i1]>=sizes[i2])
		  	{
		  		mapper[i2]=mapper[i1];
		  		sizes[i1]+=sizes[i2];
			  }
			  else
			  {
			  	mapper[i1]=mapper[i2];
			  	sizes[i2]+=sizes[i1];
			  }
		  }
		  
		}
		i++;
		j--;
		
	}
	cout<<ans;
    return 0;
}
#include <bits/stdc++.h>

using namespace std;

using ll=long long;
#define pb push_back

int main()
{
    ll n,i,j,k;
    cin>>n;
    ll arr[n];
    ll mx=0;
    ll temp1=0,temp=0;
    for(i=0;i<n;i++)
    {
        cin>>arr[i];
        mx=max(mx,arr[i]);
        temp1=temp1+arr[i];
        temp=temp1+temp;
        cout<<(i+1)*mx+temp<<"\n";
    }

    return 0;
}
