#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int a[N << 1], pos[N], maxx[N], minn[N];
int n, m;
void add(int x, int y) {
  for (; x <= n + m; x += x & -x) a[x] += y;
}
int ask(int x) {
  int ans = 0;
  for (; x; x -= x & -x) ans += a[x];
  return ans;
}
int main() {
  int t;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    pos[i] = i + m;
    minn[i] = maxx[i] = i;
    add(i + m, 1);
  }
  for (int i = 0; i < m; i++) {
    scanf("%d", &t);
    minn[t] = 1;
    maxx[t] = max(maxx[t], ask(pos[t]));
    add(pos[t], -1);
    pos[t] = m - i;
    add(pos[t], 1);
  }
  for (int i = 1; i <= n; i++) {
    maxx[i] = max(maxx[i], ask(pos[i]));
    printf("%d %d\n", minn[i], maxx[i]);
  }
  return 0;
}
