#include <bits/stdc++.h>
using namespace std;
int aib[2 * 300010], v[300010], mini[300010], maxi[300010], f[300010],
    last[300010];
void update(int i, int n, int x) {
  if (i == 0) i = 1;
  for (; i <= n; i = i + (i & (-i))) aib[i] += x;
}
int query(int i) {
  int sol = 0;
  if (!i) return 0;
  for (; i; i = i - (i & (-i))) sol += aib[i];
  return sol;
}
int main() {
  FILE *fin = stdin;
  FILE *fout = stdout;
  int n, k, i, poz, pi;
  fscanf(fin, "%d%d", &n, &k);
  for (i = 1; i <= k; i++) {
    fscanf(fin, "%d", &v[i]);
    f[v[i]] = 1;
  }
  for (i = 1; i <= n; i++) {
    if (f[i])
      mini[i] = 1;
    else
      mini[i] = i;
    maxi[i] = i;
    last[i] = n - i + 1;
    update(i, n + k, 1);
  }
  for (i = 1; i <= k; i++) {
    pi = last[v[i]];
    last[v[i]] = n + i;
    poz = n - query(pi) + 1;
    maxi[v[i]] = max(maxi[v[i]], poz);
    update(n + i, n + k, 1);
    update(pi, n + k, -1);
  }
  for (i = 1; i <= n; i++) {
    poz = n - query(last[i]) + 1;
    maxi[i] = max(maxi[i], poz);
  }
  for (i = 1; i <= n; i++) {
    fprintf(fout, "%d %d\n", mini[i], maxi[i]);
  }
  return 0;
}
