#include <bits/stdc++.h>
using namespace std;
int readin() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
long long rd(long long x) {
  long long k = 1;
  int i;
  for (i = 1; i <= 7; i++) {
    k = (k * rand()) % x;
  }
  return (k | rand()) % x + 1;
}
long long qmod(long long a, long long b, long long mod) {
  long long r = 1;
  while (b) {
    if (b & 1) r = r * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return r;
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0 && b == 0) return -1;
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
long long niyuan(long long a, long long n) {
  long long x, y;
  long long d = exgcd(a, n, x, y);
  if (d == 1) return (x % n + n) % n;
  return -1;
}
using namespace std;
int mn[600007], mx[600007], a[600007], pos[600007], sum[600007];
int n, m;
int lowbit(int x) { return x & (-x); }
void add(int x, int val) {
  while (x < 600007) {
    sum[x] += val;
    x += lowbit(x);
  }
}
int ask(int x) {
  int res = 0;
  while (x) {
    res += sum[x];
    x -= lowbit(x);
  }
  return res;
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    mn[i] = mx[i] = i;
    pos[i] = i + m;
    add(pos[i], 1);
  }
  for (int i = 0; i < m; ++i) {
    cin >> a[i];
    mn[a[i]] = 1;
    int p = a[i];
    mx[p] = max(mx[p], ask(pos[p]));
    add(pos[p], -1);
    pos[p] = m - i;
    add(pos[p], 1);
  }
  for (int i = 1; i <= n; ++i) mx[i] = max(mx[i], ask(pos[i]));
  for (int i = 1; i <= n; ++i) cout << mn[i] << ' ' << mx[i] << '\n';
  return 0;
}
