#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
using namespace std;
const int N = 500000 + 10;
const long long MOD = 1000000000 + 7;
const long long INF = 2000000010;
const long long LOG = 20;
int n, a[N], inv[N], ind[N], fen[2][N];
long long seg[2][N << 2], lazy[2][N << 2];
inline bool cmp(int x, int y) { return a[x] < a[y]; }
inline void modify(int ind, int id, long long x) {
  seg[ind][id] += x;
  lazy[ind][id] += x;
  return;
}
inline void shift(int ind, int id) {
  modify(ind, id << 1, lazy[ind][id]);
  modify(ind, id << 1 | 1, lazy[ind][id]);
  lazy[ind][id] = 0;
  return;
}
inline void Add(int ind, int id, int x) {
  for (; id < N; id += id & (-id)) fen[ind][id] += x;
  return;
}
inline int Get(int ind, int id) {
  int res = 0;
  for (; id > 0; id -= id & (-id)) res += fen[ind][id];
  return res;
}
void add(int ind, int id, int lq, int rq, long long x, int l, int r) {
  if (rq <= l || r <= lq) return;
  if (lq <= l && r <= rq) {
    modify(ind, id, x);
    return;
  }
  int md = (l + r) >> 1;
  shift(ind, id);
  add(ind, id << 1, lq, rq, x, l, md);
  add(ind, id << 1 | 1, lq, rq, x, md, r);
  if (ind == 0)
    seg[ind][id] = min(seg[ind][id << 1], seg[ind][id << 1 | 1]);
  else
    seg[ind][id] = max(seg[ind][id << 1], seg[ind][id << 1 | 1]);
  return;
}
int get(int id, int lq, int rq, int l, int r) {
  if (rq <= l || r <= lq) return INF;
  if (lq <= l && r <= rq) return seg[0][id];
  int md = (l + r) >> 1;
  shift(0, id);
  return min(get(id << 1, lq, rq, l, md), get(id << 1 | 1, lq, rq, md, r));
}
int BS(int id, int l, int r) {
  if (r - l == 1) return l;
  shift(1, id);
  int md = (l + r) >> 1;
  if (seg[1][id << 1] >= 0) return BS(id << 1, l, md);
  return BS(id << 1 | 1, md, r);
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    ind[i] = i;
  }
  sort(ind + 1, ind + n + 1, cmp);
  for (int i = 1; i <= n; i++) inv[ind[i]] = i;
  add(0, 1, 1, n + 1, INF, 1, n + 1);
  add(1, 1, 1, n + 1, -INF, 1, n + 1);
  for (int i = 1; i <= n; i++) {
    add(1, 1, inv[i], inv[i] + 1, +INF + a[i], 1, n + 1);
    add(0, 1, inv[i], inv[i] + 1, -INF + a[i], 1, n + 1);
    add(1, 1, inv[i] + 1, n + 1, 1, 1, n + 1);
    add(0, 1, 1, inv[i], 1, 1, n + 1);
    Add(0, 1, 1);
    Add(0, inv[i], -1);
    Add(1, inv[i] + 1, 1);
    if (seg[1][1] < 0) {
      printf("%d\n", -i);
      continue;
    }
    int koj = BS(1, 1, n + 1);
    int val = -Get(1, koj);
    val = min(val + 1, a[ind[koj]]);
    printf("%d\n", min(val + Get(0, koj), get(1, koj + 1, n + 1, 1, n + 1)));
  }
  return 0;
}
