#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
const int maxm = 6e5 + 10;
const long double pi = acos(-1.0L);
const long long int mod = 1e9 + 7;
int tree[maxm], n;
int mi[maxn], mx[maxn], pos[maxn];
int lowbit(int i) { return i & (-i); }
void add(int i, int c) {
  while (i < maxm) {
    tree[i] += c;
    i += lowbit(i);
  }
}
int get_sum(int i) {
  int res = 0;
  while (i > 0) {
    res += tree[i];
    i -= lowbit(i);
  }
  return res;
}
int main() {
  int m, p;
  while (scanf("%d%d", &n, &m) != EOF) {
    p = m;
    memset(tree, 0, sizeof(tree));
    for (int i = 1; i <= n; i++) {
      mi[i] = i;
      mx[i] = i;
      pos[i] = p + i;
      add(pos[i], 1);
    }
    int x;
    int top = m;
    while (m--) {
      scanf("%d", &x);
      int temp = get_sum(pos[x]);
      mx[x] = max(mx[x], temp);
      mi[x] = 1;
      add(pos[x], -1);
      pos[x] = top--;
      add(pos[x], 1);
    }
    for (int i = 1; i <= n; i++) {
      int temp = get_sum(pos[i]);
      mx[i] = max(mx[i], temp);
    }
    for (int i = 1; i <= n; i++) {
      printf("%d %d\n", mi[i], mx[i]);
    }
  }
  return 0;
}
