#include <bits/stdc++.h>   using namespace std;   template <typename T1, typename T2>   inline T1 max(T1 a, T2 b) {     return a < b ? b : a;   }   template <typename T1, typename T2>   inline T1 min(T1 a, T2 b) {     return a < b ? a : b;   }   const char lf =   n ;   namespace ae86 {   const int bufl = 1 << 15;   char buf[bufl], *s = buf, *t = buf;   inline int fetch() {     if (s == t) {       t = (s = buf) + fread(buf, 1, bufl, stdin);       if (s == t) return EOF;     }     return *s++;   }   inline int ty() {     int a = 0;     int b = 1, c = fetch();     while (!isdigit(c)) b ^= c ==  - , c = fetch();     while (isdigit(c)) a = a * 10 + c - 48, c = fetch();     return b ? a : -a;   }   }  // namespace ae86   using ae86::ty;   const int _ = 500007, __ = _ << 1, inf = 0x3f3f3f3f;   struct cxk {     int v, len;     cxk(int v_ = inf, int len_ = 0) { v = v_, len = len_; }     int f(int x) { return min(x + len, v); }     friend cxk operator+(cxk a, cxk b) {       return cxk(min(a.v + b.len, b.v), a.len + b.len);     }   };   struct sgt {     static const int _t = __ << 2;     cxk t[_t];     int mx[_t];     void up(int x) {       t[x] = t[(x << 1)] + t[(x << 1 | 1)];       mx[x] = max(mx[(x << 1)], mx[(x << 1 | 1)]);     }     void plant(int x, int l, int r) {       t[x] = cxk(), mx[x] = -inf;       if (l == r) return;       plant((x << 1), l, ((l + r) >> 1)),           plant((x << 1 | 1), ((l + r) >> 1) + 1, r), up(x);     }     void change(int x, int l, int r, int tar, int dlt) {       if (l == r) {         t[x].len++, t[x].v = dlt, mx[x] = max(mx[x], dlt);         return;       }       if (tar <= ((l + r) >> 1))         change((x << 1), l, ((l + r) >> 1), tar, dlt);       else         change((x << 1 | 1), ((l + r) >> 1) + 1, r, tar, dlt);       up(x);     }     int findlen(int x, int l, int r, int tl, int tr) {       if (tl <= l && r <= tr) return t[x].len;       if (tr <= ((l + r) >> 1))         return findlen((x << 1), l, ((l + r) >> 1), tl, tr);       if (tl > ((l + r) >> 1))         return findlen((x << 1 | 1), ((l + r) >> 1) + 1, r, tl, tr);       return findlen((x << 1), l, ((l + r) >> 1), tl, tr) +              findlen((x << 1 | 1), ((l + r) >> 1) + 1, r, tl, tr);     }     int findmx(int x, int l, int r, int tl, int tr) {       if (tl <= l && r <= tr) return mx[x];       if (tr <= ((l + r) >> 1))         return findmx((x << 1), l, ((l + r) >> 1), tl, tr);       if (tl > ((l + r) >> 1))         return findmx((x << 1 | 1), ((l + r) >> 1) + 1, r, tl, tr);       return max(findmx((x << 1), l, ((l + r) >> 1), tl, tr),                  findmx((x << 1 | 1), ((l + r) >> 1) + 1, r, tl, tr));     }     cxk findcxk(int x, int l, int r, int tl, int tr) {       if (tl <= l && r <= tr) return t[x];       if (tr <= ((l + r) >> 1))         return findcxk((x << 1), l, ((l + r) >> 1), tl, tr);       if (tl > ((l + r) >> 1))         return findcxk((x << 1 | 1), ((l + r) >> 1) + 1, r, tl, tr);       return findcxk((x << 1), l, ((l + r) >> 1), tl, tr) +              findcxk((x << 1 | 1), ((l + r) >> 1) + 1, r, tl, tr);     }   } t;   int n, val[_], rk[_] = {0};   pair<int, int> temp[_];   int able(int x) { return t.findmx(1, 1, n, 1, x) <= -t.findlen(1, 1, n, 1, x); }   int main() {     ios::sync_with_stdio(0), cout.tie(nullptr);     n = ty();     for (int i = 1; i <= n; i++) val[i] = ty(), temp[i] = make_pair(val[i], i);     sort(temp + 1, temp + n + 1);     for (int i = 1; i <= n; i++) rk[temp[i].second] = i;     t.plant(1, 1, n);     for (int i = 1; i <= n; i++) {       t.change(1, 1, n, rk[i], temp[rk[i]].first);       int l = 1, r = n, ans = -1;       while (r >= l) {         int mid = (l + r) >> 1;         if (able(mid))           ans = mid, l = mid + 1;         else           r = mid - 1;       }       if (ans < 0)         cout << t.findcxk(1, 1, n, 1, n).f(0) << lf;       else {         int ps = t.findlen(1, 1, n, 1, ans);         if (ans >= n)           cout << -ps << lf;         else           cout << t.findcxk(1, 1, n, ans + 1, n).f(-ps) << lf;       }     }     return 0;   }   