#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int a[N];
int tr[N << 3];
int n, m;
int f[N];
int T;
void Add(int x, int y) {
  for (; x <= T; x += x & -x) tr[x] += y;
}
int Ask(int x) {
  int S = 0;
  for (; x; x -= x & -x) S += tr[x];
  return S;
}
int L[N], R[N];
int g[N];
int main() {
  cin >> n >> m;
  T = n + m;
  for (int i = 1; i <= m; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) Add(i, 1);
  for (int i = 1; i <= n; i++) f[i] = n - i + 1;
  for (int i = 1; i <= n; i++) L[i] = R[i] = i;
  for (int i = 1; i <= m; i++) {
    int x = f[a[i]];
    L[a[i]] = 1;
    int now = n + 1 - Ask(x);
    R[a[i]] = max(R[a[i]], now);
    f[a[i]] = n + i;
    Add(x, -1);
    Add(n + i, 1);
  }
  int cnt = 0;
  for (int i = m; i; i--) {
    if (g[a[i]]) continue;
    cnt++;
    g[a[i]] = 1;
    R[a[i]] = max(R[a[i]], cnt);
  }
  for (int i = 1; i <= n; i++) {
    if (g[i]) continue;
    cnt++;
    g[i] = 1;
    R[i] = max(R[i], cnt);
  }
  for (int i = 1; i <= n; i++) printf("%d %d\n", L[i], R[i]);
}
