#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
int tree[MAXN << 1];
int A[MAXN];
int n, m;
int L[MAXN], R[MAXN], pos[MAXN];
inline int sum(int p) {
  int res = 0;
  for (; p > 0; p -= p & -p) res += tree[p];
  return res;
}
inline void add(int p, int val) {
  for (; p <= n + m; p += p & -p) tree[p] += val;
}
int main() {
  scanf("%d%d", &n, &m);
  iota(L + 1, L + n + 1, 1);
  iota(R + 1, R + n + 1, 1);
  for (int i = 1; i <= m; ++i) {
    scanf("%d", A + i);
    L[A[i]] = 1;
  }
  for (int i = 1; i <= n; ++i) pos[i] = i + m;
  for (int i = 1; i <= n; ++i) add(pos[i], 1);
  for (int i = 1; i <= m; ++i) {
    int x = A[i];
    R[x] = max(R[x], sum(pos[x]));
    add(pos[x], -1);
    pos[x] = m - i + 1;
    add(pos[x], 1);
  }
  for (int i = 1; i <= n; ++i) R[i] = max(R[i], sum(pos[i]));
  for (int i = 1; i <= n; ++i) printf("%d %d\n", L[i], R[i]);
  return 0;
}
