#include <bits/stdc++.h>
int n, m;
int L[600005], R[600005], pos[600005], c[600005];
inline void update(int x, int v) {
  for (; x <= n + m; x += x & (-x)) c[x] += v;
}
inline int ask(int x) {
  int res = 0;
  for (; x; x -= x & (-x)) res += c[x];
  return res;
}
inline int read() {
  register int x = 0, f = 1;
  register char s = getchar();
  while (s > '9' || s < '0') {
    if (s == '-') f = -1;
    s = getchar();
  }
  while (s >= '0' && s <= '9') {
    x = x * 10 + s - '0';
    s = getchar();
  }
  return x * f;
}
int main() {
  n = read(), m = read();
  int now = m;
  for (register int i = 1; i <= n; ++i) {
    pos[i] = i + m;
    update(i + m, 1);
    L[i] = R[i] = i;
  }
  for (register int i = 1; i <= m; ++i) {
    int x = read();
    L[x] = 1;
    R[x] = ((R[x]) > (ask(pos[x])) ? (R[x]) : (ask(pos[x])));
    update(pos[x], -1);
    pos[x] = now;
    --now;
    update(pos[x], 1);
  }
  for (register int i = 1; i <= n; ++i)
    R[i] = ((R[i]) > (ask(pos[i])) ? (R[i]) : (ask(pos[i])));
  for (register int i = 1; i <= n; ++i) printf("%d %d\n", L[i], R[i]);
  return 0;
}
