#include <bits/stdc++.h>
using namespace std;
const int iinf = 0x3f3f3f3f;
const long long linf = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5;
int n, m, a[N], to[N], le[N], re[N];
const int T = 1e6;
using ele = int;
ele val[T];
int rt, cnt, ch[T][2], p[T], sz[T];
void clear() { cnt = 0, rt = -1; }
int newnode(ele v) {
  sz[cnt] = 1, val[cnt] = v, p[cnt] = rand();
  ch[cnt][0] = ch[cnt][1] = -1;
  return cnt++;
}
void pushup(int u) {
  sz[u] = 1;
  if (~ch[u][0]) sz[u] += sz[ch[u][0]];
  if (~ch[u][1]) sz[u] += sz[ch[u][1]];
}
int merge(int u, int v) {
  if (!~u || !~v) return ~u ? u : v;
  if (p[u] < p[v])
    return ch[u][1] = merge(ch[u][1], v), pushup(u), u;
  else
    return ch[v][0] = merge(u, ch[v][0]), pushup(v), v;
}
void split(int o, ele k, int& u, int& v) {
  if (!~o) {
    u = v = -1;
    return;
  }
  if (k < val[o])
    v = o, split(ch[o][0], k, u, ch[o][0]);
  else
    u = o, split(ch[o][1], k, ch[o][1], v);
  pushup(o);
}
void print(int u) {
  if (!~u) return;
  print(ch[u][0]), cout << val[u] << ' ', print(ch[u][1]);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m, clear();
  for (int i = (0), I = (n); i < I; i++)
    to[i] = i, rt = merge(rt, newnode(to[i]));
  iota(le, le + n, 0), iota(re, re + n, 0);
  for (int ta = (0), I = (m); ta < I; ta++) {
    int u;
    cin >> u, --u;
    int L, M, R;
    split(rt, to[u], L, R), split(L, to[u] - 1, L, M);
    re[u] = max(re[u], (~L ? sz[L] : 0)), le[u] = 0;
    rt = merge(L, R), to[u] = -ta - 1, rt = merge(newnode(to[u]), rt);
  }
  for (int i = (0), I = (n); i < I; i++) {
    int L, M, R;
    split(rt, to[i], L, R), split(L, to[i] - 1, L, M);
    re[i] = max(re[i], (~L ? sz[L] : 0)), rt = merge(merge(L, M), R);
  }
  for (int i = (0), I = (n); i < I; i++)
    cout << le[i] + 1 << " " << re[i] + 1 << '\n';
  return 0;
}
