#include <bits/stdc++.h>
using namespace std;
void ga(int N, int *A) {
  for (int i(0); i < N; i++) scanf("%d", A + i);
}
int C[333333], R[333333], W;
int gc(int a) { return C[a] = (a == C[a] ? a : gc(C[a])); }
bool con(int a, int b) {
  if (gc(a) == gc(b)) return 0;
  R[C[a]] += R[gc(b)], C[C[b]] = C[a];
  return --W, 1;
}
int N, P[333333], V[333333];
int main(void) {
  scanf("%d", &N), ga(N, P),
      (iota(C, C + N + 2, 0), fill(R, R + N + 2, 1), W = N + 2), V[N + 1] = 1;
  printf("%d", 1);
  for (int i(0); i < N; i++) {
    V[P[i]] = 1;
    if (V[P[i] + 1]) con(P[i], P[i] + 1);
    if (V[P[i] - 1]) con(P[i], P[i] - 1);
    printf(" %d", 3 + i - R[gc(N + 1)]);
  }
  puts("");
  return 0;
}
