// #pragma GCC diagnostic warning "-std=c++11"
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("O3")
// #pragma GCC optimization ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
 
// #define int long long
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define pp pop_back
#define endl '\n'
#define ff first
#define ss second
#define stop exit(0)
#define sz(x) (int)x.size()
#define pause system("pause")
#define all(x) (x).begin(),(x).end()
#define deb(x) cout << #x << "-" << x  << endl
 
typedef char chr;
typedef string str;
typedef long long ll;
typedef vector <int> vii;
typedef pair <int,int> pii;
 
const long long INF = LLONG_MAX;
const int inf = INT_MAX;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int dx[] = {0,0,-1,1};
const int dy[] = {-1,1,0,0};
const double PI = 2 * acos(0.0);

const int N = 5e5 + 5;

int n,a[N],fix[N],parent[N];
vector <vii> lst(N);
int ans;

void makeset(int x) {
    lst[x] = vector<int>(1,x);
    parent[x] = x;
}

int getparent(int x) {
    return parent[x];
}

void unionset(int a, int b) {
    a = parent[a];
    b = parent[b];
    if (a == b) return;
    if (sz(lst[a]) < sz(lst[b])) swap(a,b);
    while (sz(lst[b])) {
        int c = lst[b].back();
        parent[c] = a;
        lst[a].pb(c);
        lst[b].pp();
    }
}

inline void test_case () {  
    
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        makeset(a[i]);
    }
    for (int i = 1; i <= n; i++) {
        int ans1 = (sz(lst[getparent(a[i]-1)])+1)/2 * fix[a[i]-1] + (sz(lst[getparent(a[i]+1)])+1)/2 * fix[a[i]+1];
        if (fix[a[i]-1]) unionset(a[i],a[i]-1);
        if (fix[a[i]+1]) unionset(a[i],a[i]+1);
        int ans2 = (sz(lst[getparent(a[i])])+1)/2;
        ans += max(0,ans2-ans1);
        cout << ans << " ";
        fix[a[i]] = 1;
    }
    

}
 
signed main () {
 
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int T = 1;
    // cin >> T;
    while(T--) {
        test_case();
    }
    
    return 0;
 
}