#include <bits/stdc++.h>
using namespace std;
const int maxm = 6e5 + 5;
int l[maxm], r[maxm];
int c[maxm];
int pos[maxm];
int n, m;
int max(int a, int b) {
  if (a > b)
    return a;
  else
    return b;
}
int lowbit(int i) { return i & -i; }
void add(int i, int t) {
  while (i < maxm) {
    c[i] += t;
    i += lowbit(i);
  }
}
int ask(int i) {
  int ans = 0;
  while (i) {
    ans += c[i];
    i -= lowbit(i);
  }
  return ans;
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    l[i] = r[i] = i;
    add(i + m, 1);
    pos[i] = i + m;
  }
  int last = m;
  while (m--) {
    int x;
    cin >> x;
    l[x] = 1;
    int num = ask(pos[x]);
    r[x] = max(r[x], num);
    if (num == 1) continue;
    add(pos[x], -1);
    pos[x] = last;
    add(pos[x], 1);
    last--;
  }
  for (int i = 1; i <= n; i++) {
    r[i] = max(r[i], ask(pos[i]));
  }
  for (int i = 1; i <= n; i++) {
    cout << l[i] << ' ' << r[i] << endl;
  }
  return 0;
}
