#include <bits/stdc++.h>
using namespace std;
const long double EPS = 1e-18;
const double DEPS = 1e-9;
const long double PI = 3.141592653589793238;
const long long MOD = 998244353;
const int N = (int)(5e5) + 10;
void inp() {}
void out() {}
long long gcd(long long fx, long long fy) {
  if (!fy) return fx;
  return gcd(fy, fx % fy);
}
inline void fill(int* ar, int sz, int val) {
  for (int i = 0; i < sz; i++) {
    ar[i] = val;
  }
}
int n, m, a[N], add[N], mx[N], x, b[N], cur = 1, mn[N];
int st[4 * N];
vector<pair<int, int> > ans;
void update(int p = 1, int l = 0, int r = n - 1) {
  if (l == r) {
    st[p] = cur;
    return;
  }
  int m = (l + r) >> 1;
  if (x > m) {
    update(p * 2 + 1, m + 1, r);
  } else {
    update(p * 2, l, m);
  }
  st[p] = st[p * 2] + st[p * 2 + 1];
}
int get(int a, int b, int p = 1, int l = 0, int r = n - 1) {
  if (a > r || b < l) {
    return 0;
  }
  if (l >= a && r <= b) {
    return st[p];
  }
  int m = (l + r) >> 1;
  return get(a, b, p * 2, l, m) + get(a, b, p * 2 + 1, m + 1, r);
}
int main() {
  inp();
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    scanf("%d", &x);
    b[i] = x;
    if (a[x]) continue;
    a[x] = i + 1;
    mx[x] = x + get(x - 1, n - 1);
    mn[x] = 1;
    x--;
    update();
  }
  for (int i = 1; i <= n; i++) {
    if (!a[i]) {
      mx[i] = i + get(i, n - 1);
    }
    a[i] = 0;
  }
  memset(st, false, sizeof(st));
  for (int i = 0; i < m; i++) {
    if (a[b[i]]) {
      mx[b[i]] = max(mx[b[i]], get(a[b[i]], i, 1, 0, m - 1) + 1);
      x = a[b[i]] - 1;
      cur = 0;
      update(1, 0, m - 1);
    }
    x = i;
    cur = 1;
    update(1, 0, m - 1);
    a[b[i]] = i + 1;
  }
  for (int i = 1; i <= n; i++) {
    if (a[i]) {
      mx[i] = max(mx[i], get(a[i], m - 1, 1, 0, m - 1) + 1);
    }
    mn[i] = (mn[i] ? mn[i] : i);
    printf("%d %d\n", mn[i], mx[i]);
  }
}
