#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int res_min[N], res_max[N], bit[N], use[N], last[N];
int n, m, x;
inline void add(int x, int v) {
  for (int i = x; i <= n; i += i & -i) bit[i] += v;
}
inline int qry(int x) {
  int ret = 0;
  for (int i = x; i > 0; i ^= i & -i) ret += bit[i];
  return ret;
}
struct Node {
  int v, lc, rc;
  Node() {}
  Node(int x) : v(x), lc(0), rc(0) {}
} node[N * 30];
int rt[N], cnt = 0;
int _new_(int x = 0) {
  node[++cnt] = node[x];
  return cnt;
}
int build(int l, int r) {
  int p = _new_();
  if (l == r) return p;
  int m = (l + r) >> 1;
  node[p].lc = build(l, m), node[p].rc = build(m + 1, r);
  return p;
}
inline void upd(int p) { node[p].v = node[node[p].lc].v + node[node[p].rc].v; }
void add(int &p, int pos, int l, int r, int v) {
  p = _new_(p);
  if (l == r) {
    node[p].v += v;
    return;
  }
  int m = (l + r) >> 1;
  if (pos <= m)
    add(node[p].lc, pos, l, m, v);
  else
    add(node[p].rc, pos, m + 1, r, v);
  upd(p);
}
int qry(int p, int ql, int qr, int l, int r) {
  if (l > qr || r < ql) return 0;
  if (l >= ql && r <= qr) return node[p].v;
  int m = (l + r) >> 1, ret = 0;
  if (ql <= m) ret += qry(node[p].lc, ql, qr, l, m);
  if (qr > m) ret += qry(node[p].rc, ql, qr, m + 1, r);
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) res_min[i] = res_max[i] = i;
  rt[0] = build(0, m);
  for (int i = 1; i <= m; i++) {
    cin >> x;
    res_min[x] = 1;
    rt[i] = rt[i - 1];
    if (!use[x]) {
      res_max[x] = max(res_max[x], x + qry(n) - qry(x));
      add(x, 1);
      use[x] = 1;
    } else
      res_max[x] = max(res_max[x], 1 + qry(rt[i], 0, last[x], 0, m) -
                                       qry(rt[last[x]], 0, last[x], 0, m));
    add(rt[i], last[x], 0, m, 1);
    last[x] = i;
  }
  for (int i = 1; i <= n; i++)
    if (use[i])
      res_max[i] = max(res_max[i], 1 + qry(rt[m], 0, last[i], 0, m) -
                                       qry(rt[last[i]], 0, last[i], 0, m));
  for (int i = 1; i <= n; i++)
    if (!use[i]) res_max[i] += qry(n) - qry(i);
  for (int i = 1; i <= n; i++) cout << res_min[i] << " " << res_max[i] << endl;
  return 0;
}
