#include <bits/stdc++.h>
using namespace std;
bool ada[300000 + 2];
int n;
int p[300000 + 2];
int kiri[300000 + 2];
int kanan[300000 + 2];
long long BIT[2][300000 + 2];
long long quer(int id, int idx) {
  if (idx == 0) {
    return 0;
  }
  return BIT[id][idx] + quer(id, idx - (idx & (-idx)));
}
long long range(int id, int aw, int ak) {
  return quer(id, ak) - quer(id, aw - 1);
}
void update(int id, int idx, long long val) {
  if (idx > n + 1) {
    return;
  }
  BIT[id][idx] += val;
  update(id, idx + (idx & (-idx)), val);
}
int ca(int mas) {
  if (mas == kanan[mas]) {
    return mas;
  }
  return kanan[mas] = ca(kanan[mas]);
}
int ci(int mas) {
  if (mas == kiri[mas]) {
    return mas;
  }
  return kiri[mas] = ci(kiri[mas]);
}
void gba(int a, int b) {
  int aa = ca(a);
  int bb = ca(b);
  if (aa == bb) {
    return;
  }
  kanan[aa] = bb;
}
void gbi(int a, int b) {
  int aa = ci(a);
  int bb = ci(b);
  if (aa == bb) {
    return;
  }
  kiri[bb] = aa;
}
void gb(int a, int b) {
  gbi(a, b);
  gba(a, b);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", p + i);
  }
  for (int i = 1; i <= n + 1; i++) {
    kiri[i] = i;
    kanan[i] = i;
  }
  ada[n + 1] = 1;
  update(0, n + 1, 1);
  update(1, n + 1, 1);
  long long ans = 1;
  printf("1");
  for (int i = 1; i <= n; i++) {
    if (!ada[p[i] - 1] && !ada[p[i] + 1]) {
      update(0, p[i], 1);
      update(1, p[i], 1);
      ans++;
    } else if (!ada[p[i] + 1]) {
      gb(p[i] - 1, p[i]);
      update(1, p[i], 1);
    } else if (!ada[p[i] - 1]) {
      gb(p[i], p[i] + 1);
      update(0, p[i], 1);
      update(0, ca(p[i]), -1);
      update(1, p[i], 1);
    } else {
      gb(p[i] - 1, p[i]);
      gb(p[i], p[i] + 1);
      update(0, p[i] + 1, -1);
      update(1, p[i], 1);
      ans--;
    }
    ada[p[i]] = 1;
    ans = range(1, 1, ci(n + 1) - 1);
    printf(" %lld", ans + 1);
  }
  printf("\n");
}
