#include <bits/stdc++.h>
using namespace std;
const int maxn = 300000 + 3000;
int n, m;
int a[maxn], l[maxn], r[maxn], pos[maxn];
struct Segtree {
  int l, r;
  int val;
} node[maxn << 3];
inline int read() {
  int x;
  scanf("%d", &x);
  return x;
}
inline void build(int p, int l, int r) {
  node[p].l = l, node[p].r = r;
  node[p].val = 0;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
}
inline void update(int p) {
  node[p].val = node[p << 1].val + node[p << 1 | 1].val;
}
inline void change(int p, int vl, int vr, int c) {
  if (node[p].l == vl && node[p].r == vr) {
    node[p].val += c;
    return;
  }
  int mid = (node[p].l + node[p].r) >> 1;
  if (vr <= mid)
    change(p << 1, vl, vr, c);
  else
    change(p << 1 | 1, vl, vr, c);
  update(p);
}
inline int query(int p, int vl, int vr) {
  if (node[p].l == vl && node[p].r == vr) return node[p].val;
  int mid = (node[p].l + node[p].r) >> 1;
  if (vr <= mid)
    return query(p << 1, vl, vr);
  else if (vl > mid)
    return query(p << 1 | 1, vl, vr);
  else
    return query(p << 1, vl, mid) + query(p << 1 | 1, mid + 1, vr);
}
int main() {
  n = read(), m = read();
  build(1, 1, n + m);
  for (int i = 1; i <= n; ++i)
    change(1, m + i, m + i, 1), pos[i] = m + i, l[i] = r[i] = i;
  for (int i = 1; i <= m; ++i) {
    scanf("%d", &a[i]);
    l[a[i]] = min(1, l[a[i]]);
    r[a[i]] = max(r[a[i]], query(1, 1, pos[a[i]]));
    change(1, pos[a[i]], pos[a[i]], -1);
    pos[a[i]] = m - i + 1;
    change(1, pos[a[i]], pos[a[i]], 1);
  }
  for (int i = 1; i <= n; ++i) {
    r[i] = max(r[i], query(1, 1, pos[i]));
    printf("%d %d\n", l[i], r[i]);
  }
  return 0;
}
