#include <bits/stdc++.h>
using namespace std;
set<pair<int, int>> s;
int main() {
  int n;
  scanf("%d", &n);
  printf("1");
  int64_t total = 1;
  for (int i = 0; i < n; i++) {
    int p;
    scanf("%d", &p);
    int pl = p;
    int pr = p;
    auto it = s.lower_bound({p + 1, 0});
    if (it != s.end()) {
      if (it->first == p + 1) {
        pr = it->second;
        if (it->second != n) total -= it->second - it->first + 1;
        s.erase(it);
      }
    }
    it = s.lower_bound({p, 0});
    if (it != s.begin()) {
      it--;
      if (it->second == p - 1) {
        pl = it->first;
        if (it->second != n) total -= it->second - it->first + 1;
        s.erase(it);
      }
    }
    if (pr != n) total += pr - pl + 1;
    s.insert({pl, pr});
    printf(" %lld", total);
  }
  printf("\n");
}
