#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long binExp(long long x, long long n) {
  long long r = 1;
  while (n > 0) {
    if (n % 2 == 1) r = r * x;
    x = x * x;
    n = n / 2;
  }
  return r;
}
long long modbinExp(long long x, long long n, long long M) {
  long long r = 1;
  while (n > 0) {
    if (n % 2 == 1) r = (r * x) % M;
    x = (x * x) % M;
    n = n / 2;
  }
  return r;
}
long long BIT[2 * 300005];
void update(long long idx, long long val) {
  while (idx < (2 * 300005)) BIT[idx] += val, idx += -idx & idx;
}
long long sum(long long idx) {
  long long s = 0;
  while (idx > 0) s += BIT[idx], idx -= -idx & idx;
  return s;
}
long long index_trace[300005], maxi[300005], mini[300005];
long long beg = 300005;
void solve() {
  long long n, m, x, y;
  cin >> n >> m;
  for (long long i = 1; i <= n; i++)
    update(beg + i, 1), index_trace[i] = beg + i, mini[i] = i;
  while (m--) {
    cin >> y;
    mini[y] = 1;
    beg--;
    maxi[y] = max(maxi[y], sum(index_trace[y]));
    update(index_trace[y], -1);
    update(beg, 1);
    index_trace[y] = beg;
  }
  for (long long i = 1; i <= n; i++)
    maxi[i] = max(maxi[i], sum(index_trace[i]));
  for (long long i = 1; i <= n; i++) cout << mini[i] << " " << maxi[i] << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  long long t;
  t = 1;
  while (t--) {
    solve();
  }
}
