#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 9;
struct pp {
  int id, vl;
  bool operator<(const pp &temp) const {
    if (vl == temp.vl) return id < temp.id;
    return vl < temp.vl;
  }
};
int a[501000], n;
pp b[501000], now;
int binary(int left, int right, pp now) {
  int mid;
  while (left <= right) {
    mid = (left + right) >> 1;
    if (b[mid] < now)
      left = mid + 1;
    else if (now < b[mid])
      right = mid - 1;
    else
      return mid;
  }
}
struct segment_tree {
  int l, r, add, vl, max_vl, min_vl, a;
};
segment_tree tree[1 << 20];
void build(int left, int right, int id) {
  int l = 2 * id + 1, r = 2 * id + 2, mid = (left + right) >> 1;
  tree[id].l = left;
  tree[id].r = right;
  tree[id].add = 0;
  tree[id].min_vl = tree[id].vl = inf;
  tree[id].max_vl = -inf;
  if (left == right) return;
  build(left, mid, l);
  build(mid + 1, right, r);
}
void zz(int id) {
  int l = 2 * id + 1, r = 2 * id + 2;
  bool con = false;
  if (tree[id].add == 0) return;
  if (tree[id].vl != inf) {
    if (tree[id].l != tree[id].r) {
      tree[l].add += tree[id].add;
      tree[r].add += tree[id].add;
    }
    tree[id].vl += tree[id].add;
    tree[id].min_vl += tree[id].add;
    tree[id].max_vl += tree[id].add;
  }
  tree[id].add = 0;
}
int query(int pos, int id) {
  int l = 2 * id + 1, r = 2 * id + 2, ret;
  zz(id);
  if (tree[id].l == tree[id].r) return tree[id].vl;
  if (tree[l].r < pos)
    ret = query(pos, r);
  else
    ret = query(pos, l);
  return ret;
}
bool modify(int left, int right, int su, int id) {
  int l = 2 * id + 1, r = 2 * id + 2;
  zz(id);
  if (tree[id].r < left || tree[id].l > right || tree[id].vl == inf)
    return true;
  if (tree[id].l >= left && tree[id].r <= right) {
    if (su > 0) {
      if (tree[id].max_vl < -1 || tree[id].min_vl > 0) {
        tree[id].add++;
        zz(id);
        return true;
      }
    } else {
      if (tree[id].max_vl < 0 || tree[id].min_vl > 1) {
        tree[id].add--;
        zz(id);
        return true;
      }
    }
  }
  if (tree[id].l == tree[id].r) {
    if (su > 0) {
      tree[id].max_vl++;
      tree[id].min_vl++;
    } else {
      tree[id].max_vl--;
      tree[id].min_vl--;
    }
    return false;
  }
  bool ret = false;
  if (modify(left, right, su, l))
    ret = modify(left, right, su, r);
  else
    zz(r);
  tree[id].vl = min(tree[l].vl, tree[r].vl);
  tree[id].min_vl = min(tree[l].min_vl, tree[r].min_vl);
  tree[id].max_vl = max(tree[l].max_vl, tree[r].max_vl);
  return ret;
}
void insert(segment_tree awp, int id) {
  int l = 2 * id + 1, r = 2 * id + 2;
  zz(id);
  if (tree[id].l == tree[id].r) {
    tree[id] = awp;
    return;
  }
  if (tree[l].r < awp.l) {
    insert(awp, r);
    zz(l);
  } else {
    insert(awp, l);
    zz(r);
  }
  tree[id].vl = min(tree[l].vl, tree[r].vl);
  tree[id].min_vl = min(tree[l].min_vl, tree[r].min_vl);
  tree[id].max_vl = max(tree[l].max_vl, tree[r].max_vl);
}
int got(int left, int right, int id) {
  int l = 2 * id + 1, r = 2 * id + 2;
  zz(id);
  if (tree[id].r < left || tree[id].l > right || tree[id].vl == inf) return inf;
  if (tree[id].l == tree[id].r) return tree[id].vl;
  int ret = got(left, right, r);
  if (ret == inf) ret = got(left, right, l);
  return ret;
}
segment_tree got_upper_bound(int left, int right, int id) {
  segment_tree ret;
  int l = 2 * id + 1, r = 2 * id + 2;
  zz(id);
  if (tree[id].r < left || tree[id].l > right || tree[id].vl == inf) {
    ret.vl = inf;
    return ret;
  }
  if (tree[id].l == tree[id].r) return tree[id];
  ret = got_upper_bound(left, right, l);
  if (ret.vl == inf) ret = got_upper_bound(left, right, r);
  return ret;
}
segment_tree got_lower_bound(int left, int right, int id) {
  segment_tree ret;
  int l = 2 * id + 1, r = 2 * id + 2;
  zz(id);
  if (tree[id].r < left || tree[id].l > right || tree[id].vl == inf) {
    ret.vl = inf;
    return ret;
  }
  if (tree[id].l == tree[id].r) return tree[id];
  ret = got_lower_bound(left, right, r);
  if (ret.vl == inf) ret = got_lower_bound(left, right, l);
  return ret;
}
int main() {
  scanf("%d", &n);
  int i, j, s, p, q, id, vl, su, ans;
  for (i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    b[i].vl = a[i];
    b[i].id = i;
  }
  sort(b, b + n);
  build(0, n - 1, 0);
  for (i = 0; i < n; i++) {
    now.id = i;
    now.vl = a[i];
    id = binary(0, n - 1, now);
    if (id == 0)
      vl = inf;
    else
      vl = got(0, id - 1, 0);
    if (vl == inf) vl = 0;
    if (vl < a[i])
      su = 1;
    else if (vl > a[i])
      su = -1;
    else
      su = 0;
    if (su != 0) modify(id + 1, n - 1, su, 0);
    segment_tree now = got_upper_bound(id + 1, n - 1, 0);
    if (now.vl < inf) {
      int ex_vl;
      if (su + vl > now.a)
        ex_vl = su + vl - 1;
      else if (su + vl < now.a)
        ex_vl = su + vl + 1;
      else
        ex_vl = su + vl;
      while (ex_vl != now.vl) {
        printf("now.l=%d,i=%d,ex_vl=%d,now.vl=%d,now.a=%d\n", now.l, i, ex_vl,
               now.vl, now.a);
        printf("su+vl=%d,vl=%d,su=%d\n", su + vl, vl, su);
      }
      now.min_vl = now.max_vl = su + vl - now.a;
      insert(now, 0);
    }
    now = got_lower_bound(0, id - 1, 0);
    if (now.vl == inf) now.vl = 0;
    segment_tree nw;
    nw.l = nw.r = id;
    nw.vl = su + vl;
    nw.max_vl = nw.min_vl = now.vl - a[i];
    nw.add = 0;
    nw.a = a[i];
    insert(nw, 0);
    ans = got(0, n - 1, 0);
    printf("%d\n", ans);
  }
  return 0;
}
