#include <bits/stdc++.h>
using namespace std;
const long long inf = 0x3f3f3f3f;
const int N = 1e6 + 10;
const long long mod = 1e9 + 7;
const int base = 131;
const double pi = acos(-1);
long long a[N], b[N], n, m, f[N], vis[N], siz[N];
long long ans, flag, sum;
int fid(int x) {
  if (x == f[x])
    return x;
  else
    return f[x] = fid(f[x]);
}
void join(int x, int y) {
  int fx = fid(x), fy = fid(y);
  if (fx != fy) {
    f[fx] = fy;
    siz[fy] += siz[fx];
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    f[i] = i;
    siz[i] = 1;
    cin >> a[i];
  }
  cout << 1 << " ";
  ans = 1;
  for (int i = 1; i <= n; i++) {
    if (a[i] != n) {
      ans++;
    }
    if (vis[a[i] - 1] && vis[a[i] + 1]) {
      int x = siz[fid(a[i] - 1)] + 1;
      join(a[i] - 1, a[i]);
      join(a[i], a[i] + 1);
      if (fid(a[i]) == n) ans -= x;
    } else if (vis[a[i] - 1]) {
      int x = siz[fid(a[i] - 1)];
      join(a[i] - 1, a[i]);
      if (a[i] == n) {
        ans -= siz[fid(a[i])] - 1;
      }
    } else if (vis[a[i] + 1]) {
      int x = siz[fid(a[i] - 1)];
      join(a[i], a[i] + 1);
      if (fid(a[i]) == fid(n)) {
        ans--;
      }
    }
    vis[a[i]] = 1;
    cout << ans << " ";
  }
}
