#include<bits/stdc++.h>
#define _forp(i,x,y) for(int i=x; i>=y; i--)
#define _for(i,x,y) for(int i=x; i<=y; i++)
using namespace std;
const int MAXN=5e5+5;
typedef long long ll;
#define int long long
int a[MAXN];
bool b[5*MAXN];
int sz[5*MAXN];
int fa[5*MAXN];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
signed main(){
	int n,ans=0;
	cin>>n;
	_for(i,0,5e5){
		fa[i]=i;
		sz[i]=1;
	}
	_for(i,1,n){
		cin>>a[i];
		if(b[a[i]]){
			cout<<ans<<" ";
			continue;
		}
		b[a[i]]=1;
		if(b[a[i]-1]&&b[a[i]+1]){
			int fa1=find(b[a[i]-1]),fa2=find(b[a[i]+1]);
			ans=ans-((sz[fa1]+1)>>1)-((sz[fa2]+1)>>1);
			sz[a[i]]=sz[fa1]+sz[fa2]+1;
			fa[fa2]=a[i];
			fa[fa1]=a[i];
			ans=ans+((sz[a[i]]+1)>>1);
			
		}
		else if(b[a[i]-1]){
			int fat=find(b[a[i]-1]);
			ans=ans-((sz[fat]+1)>>1);
			sz[a[i]]=sz[fat]+1;
			fa[fat]=a[i];
			ans=ans+((sz[a[i]]+1)>>1);
			
			
		}
		else if(b[a[i]+1]){
			int fat=find(b[a[i]+1]);
			ans=ans-((sz[fat]+1)>>1);
			sz[a[i]]=sz[fat]+1;
			fa[fat]=a[i];
			ans=ans+((sz[a[i]]+1)>>1);
			
		}
		else ans++;
		
		cout<<ans<<" ";
	}
	
	return 0;
}