#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
struct DP {
  int mn, t;
  inline int val(int x) { return min(x + t, mn); }
};
inline DP operator*(DP a, DP b) {
  a.t += b.t;
  a.mn = min(b.mn, a.mn + b.t);
  return a;
}
struct TNode {
  int l, r, mx;
  DP v;
} t[N << 2];
inline int lc(int pos) { return pos << 1; }
inline int rc(int pos) { return pos << 1 | 1; }
void build(int pos, int l, int r) {
  t[pos].l = l;
  t[pos].r = r;
  t[pos].mx = INT_MIN / 2;
  t[pos].v.mn = INT_MAX / 2;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(lc(pos), l, mid);
  build(rc(pos), mid + 1, r);
  t[pos].v = t[lc(pos)].v * t[rc(pos)].v;
}
void modify(int pos, int p, int v) {
  t[pos].mx = max(t[pos].mx, v);
  if (t[pos].l == t[pos].r) {
    ++t[pos].v.t;
    t[pos].v.mn = v;
    return;
  }
  int mid = (t[pos].l + t[pos].r) >> 1;
  if (p <= mid)
    modify(lc(pos), p, v);
  else
    modify(rc(pos), p, v);
  t[pos].v = t[lc(pos)].v * t[rc(pos)].v;
}
int calc(int pos, int l, int r) {
  if (t[pos].l == l && t[pos].r == r) return t[pos].v.t;
  int mid = (t[pos].l + t[pos].r) >> 1;
  if (r <= mid)
    return calc(lc(pos), l, r);
  else if (l > mid)
    return calc(rc(pos), l, r);
  else
    return calc(lc(pos), l, mid) + calc(rc(pos), mid + 1, r);
}
int find(int pos, int l, int r) {
  if (t[pos].l == l && t[pos].r == r) return t[pos].mx;
  int mid = (t[pos].l + t[pos].r) >> 1;
  if (r <= mid)
    return find(lc(pos), l, r);
  else if (l > mid)
    return find(rc(pos), l, r);
  return max(find(lc(pos), l, mid), find(rc(pos), mid + 1, r));
}
DP query(int pos, int l, int r) {
  if (t[pos].l == l && t[pos].r == r) return t[pos].v;
  int mid = (t[pos].l + t[pos].r) >> 1;
  if (r <= mid)
    return query(lc(pos), l, r);
  else if (l > mid)
    return query(rc(pos), l, r);
  return query(lc(pos), l, mid) * query(rc(pos), mid + 1, r);
}
inline bool check(int x) { return find(1, 1, x) <= -calc(1, 1, x); }
int n, a[N];
pair<int, int> b[N];
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i], b[i] = {a[i], i};
  sort(b + 1, b + n + 1);
  for (int i = 1; i <= n; i++) a[b[i].second] = i;
  build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    modify(1, a[i], b[a[i]].first);
    int l = 1, r = n, cur = -1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (check(mid))
        cur = mid, l = mid + 1;
      else
        r = mid - 1;
    }
    if (cur == -1)
      cout << query(1, 1, n).val(0) << '\n';
    else {
      int num = calc(1, 1, cur);
      if (cur == n) {
        cout << -num << '\n';
        continue;
      }
      cout << query(1, cur + 1, n).val(-num) << '\n';
    }
  }
  return 0;
}
