#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
int n, pos[maxn];
pair<int, int> A[maxn];
int tag[maxn << 2], val[maxn << 2], sz[maxn << 2], vmn[maxn << 2];
void pushtag(int k, int x) { tag[k] += x, val[k] += x, vmn[k] -= x; }
void pushdown(int k) {
  int& x = tag[k];
  if (x) pushtag(k << 1, x), pushtag(k << 1 | 1, x), x = 0;
}
void maintain(int k) {
  sz[k] = sz[k << 1] + sz[k << 1 | 1],
  val[k] = max(val[k << 1], val[k << 1 | 1]),
  vmn[k] = min(vmn[k << 1], vmn[k << 1 | 1]);
}
int query_sz(int k, int l, int r, int x) {
  if (r <= x) return sz[k];
  pushdown(k);
  return x <= ((l + r) >> 1)
             ? query_sz(k << 1, l, ((l + r) >> 1), x)
             : sz[k << 1] + query_sz(k << 1 | 1, ((l + r) >> 1) + 1, r, x);
}
void ins(int k, int l, int r, int x, int v1, int v2) {
  if (l == r) return val[k] = v1, vmn[k] = v2, sz[k] = 1, void();
  pushdown(k);
  x <= ((l + r) >> 1) ? ins(k << 1, l, ((l + r) >> 1), x, v1, v2)
                      : ins(k << 1 | 1, ((l + r) >> 1) + 1, r, x, v1, v2),
      maintain(k);
}
void add(int k, int l, int r, int x) {
  if (x <= l) {
    pushtag(k, 1);
    return;
  }
  pushdown(k);
  if (x <= ((l + r) >> 1)) add(k << 1, l, ((l + r) >> 1), x);
  add(k << 1 | 1, ((l + r) >> 1) + 1, r, x);
  maintain(k);
}
int query_pos(int k, int l, int r) {
  if (l == r) {
    if (val[k] < 0) return -1;
    return l;
  }
  pushdown(k);
  if (val[k << 1] >= 0) {
    return query_pos(k << 1, l, ((l + r) >> 1));
  } else {
    return query_pos(k << 1 | 1, ((l + r) >> 1) + 1, r);
  }
}
int query_min(int k, int l, int r, int x) {
  if (x <= l) return vmn[k];
  pushdown(k);
  return x <= ((l + r) >> 1)
             ? min(vmn[k << 1 | 1], query_min(k << 1, l, ((l + r) >> 1), x))
             : query_min(k << 1 | 1, ((l + r) >> 1) + 1, r, x);
}
int main() {
  cin >> n;
  for (int i = (1), iend = (n); i <= iend; ++i) {
    int x;
    scanf("%d", &x), A[i] = {x, i};
  }
  sort(A + 1, A + n + 1);
  for (int i = (1), iend = (n); i <= iend; ++i) pos[A[i].second] = i;
  memset(vmn, 0x3f, sizeof vmn);
  memset(val, -0x3f, sizeof val);
  for (int _ = (1), _end = (n); _ <= _end; ++_) {
    int p = pos[_], x = A[p].first;
    int rk = query_sz(1, 1, n, p) + 1;
    ins(1, 1, n, p, x + rk, x - rk);
    if (p < n) add(1, 1, n, p + 1);
    int pos = query_pos(1, 1, n);
    if (pos == -1) {
      printf("%d\n", -_);
      continue;
    }
    int res = -2 * (query_sz(1, 1, n, pos) - 1);
    res = min(res, query_min(1, 1, n, pos));
    printf("%d\n", _ + res);
  }
  return 0;
}
