#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, m;
int tr[N << 1], a[N], l[N], r[N], pos[N];
void add(int x, int val) {
  for (; x <= n + m; x += x & -x) tr[x] += val;
}
int get(int x) {
  int res = 0;
  for (; x; x -= x & -x) res += tr[x];
  return res;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (1); i <= (m); ++i) scanf("%d", a + i);
  for (int i = (1); i <= (n); ++i) l[i] = i;
  for (int i = (1); i <= (m); ++i) l[a[i]] = 1;
  memset(tr, 0, sizeof tr);
  for (int i = (1); i <= (n); ++i) add(pos[i] = m + i, 1);
  for (int i = (1); i <= (m); ++i) {
    int &p = pos[a[i]];
    r[a[i]] = max(r[a[i]], get(p));
    add(p, -1);
    add(p = m + 1 - i, 1);
  }
  for (int i = (1); i <= (n); ++i) r[i] = max(r[i], get(pos[i]));
  for (int i = (1); i <= (n); ++i) printf("%d %d\n", l[i], r[i]);
  return 0;
}
