#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> v;
map<int, int> mp;
struct BIT {
  vector<int> bit;
  void resize(int N) { bit.assign(N, 0); }
  void add(int i, int j) {
    i++;
    while (i < bit.size()) {
      bit[i] += j;
      i += i & -i;
    }
  }
  int sum(int i) {
    int r = 0;
    i++;
    while (i) {
      r += bit[i];
      i -= i & -i;
    }
    return r;
  }
  int rng(int lef, int rig) {
    int F = sum(rig);
    if (lef) {
      F -= sum(lef - 1);
    }
    return F;
  }
};
struct MAX_BIT {
  vector<long double> bit;
  void resize(int N) { bit.assign(N, INT_MIN); }
  void add(int i, long double j) {
    i++;
    while (i < bit.size()) {
      bit[i] = max(bit[i], j);
      i += i & -i;
    }
  }
  long double sum(int i) {
    long double r = INT_MIN;
    i++;
    while (i) {
      r = max(r, bit[i]);
      i -= i & -i;
    }
    return r;
  }
};
BIT bit;
MAX_BIT mb;
map<int, int> val;
map<int, vector<int> > pos;
vector<int> vv;
int seg[500002 * 4];
int lazy[500002 * 4];
void update(int b) {
  seg[b] += lazy[b];
  if (b * 2 + 2 < 500002 * 4) {
    lazy[b * 2 + 1] += lazy[b];
    lazy[b * 2 + 2] += lazy[b];
  }
  lazy[b] = 0;
}
inline void append(int b, int l, int r, int ll, int x) {
  update(b);
  if (ll < l || r <= ll) return;
  if (l + 1 == r) {
    seg[b] = x;
    return;
  }
  append(b * 2 + 1, l, (l + r) >> 1, ll, x);
  append(b * 2 + 2, (l + r) >> 1, r, ll, x);
  seg[b] = min(seg[b * 2 + 1], seg[b * 2 + 2]);
}
inline void add(int b, int l, int r, int ll, int rr, int x) {
  update(b);
  if (r <= ll || rr <= l) return;
  if (ll <= l && r <= rr) {
    lazy[b] += x;
    update(b);
    return;
  }
  add(b * 2 + 1, l, (l + r) >> 1, ll, rr, x);
  add(b * 2 + 2, (l + r) >> 1, r, ll, rr, x);
  seg[b] = min(seg[b * 2 + 1], seg[b * 2 + 2]);
}
inline int query(int b, int l, int r, int ll, int rr) {
  if (ll >= rr) return INT_MAX;
  update(b);
  if (r <= ll || rr <= l) return INT_MAX;
  if (ll <= l && r <= rr) {
    return seg[b];
  }
  return min(query(b * 2 + 1, l, (l + r) >> 1, ll, rr),
             query(b * 2 + 2, (l + r) >> 1, r, ll, rr));
}
int res;
int NN;
bool ok(int mid) {
  int x = bit.sum(mid);
  if (x == 0) return false;
  int ne = 0 - x;
  res = ne;
  x--;
  int y = ne;
  NN = y - x;
  return ne + 1 <= mb.sum(mid);
}
int main() {
  for (int i = 0; i < 500002 * 4; i++) seg[i] = INT_MAX;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int a;
    scanf("%d", &a);
    v.push_back(a);
    mp[a] = 0;
    vv.push_back(a);
  }
  sort(vv.begin(), vv.end());
  for (int i = 0; i < vv.size(); i++) {
    pos[vv[i]].push_back(i);
  }
  for (auto it = pos.begin(); it != pos.end(); it++) {
    sort((*it).second.begin(), (*it).second.end());
  }
  {
    int ord = 0;
    for (auto it = mp.begin(); it != mp.end(); it++) {
      (*it).second = ord;
      val[ord] = (*it).first;
      ord++;
    }
  }
  int cur = INT_MAX;
  int mx = n + 1;
  bit.resize(500002);
  mb.resize(500002);
  for (int i = 0; i < n; i++) {
    v[i] = mp[v[i]];
    int p = pos[val[v[i]]].back();
    int ord = bit.sum(p);
    int N = val[v[i]] - ord;
    pos[val[v[i]]].pop_back();
    append(0, 0, mx, p, N);
    add(0, 0, mx, p + 1, mx, -1);
    cur = min(cur, val[v[i]]);
    bit.add(p, 1);
    mb.add(p, val[v[i]]);
    int lef = 0;
    {
      int ans = INT_MAX;
      if (cur < 0) {
        int mint = 0;
        int maxt = vv.size() - 1;
        while (mint + 1 < maxt) {
          int mid = (mint + maxt) >> 1;
          if (ok(mid)) {
            maxt = mid;
          } else {
            mint = mid + 1;
          }
        }
        if (!ok(maxt)) {
          ok(maxt);
          lef = maxt + 1;
        } else {
          if (ok(mint)) {
            ok(mint - 1);
            lef = mint;
          } else {
            ok(mint);
            lef = mint + 1;
          }
        }
        ans = min(ans, NN);
      }
      ans = min(ans, 1);
      ans = min(ans, query(0, 0, mx, lef, mx));
      ans += i;
      printf("%d\n", ans);
    }
  }
  return 0;
}
