#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct BIT {
  int n;
  vector<T> dat;
  BIT(int n = 0) { initialize(n); }
  void initialize(int nin) {
    n = nin;
    dat.resize(n, 0);
  }
  T sum(int i) {
    T s = 0;
    while (i >= 0) {
      s += dat[i];
      i = (i & (i + 1)) - 1;
    }
    return s;
  }
  T sum_between(int i, int j) { return sum(j) - sum(i - 1); }
  void plus(int i, T x) {
    while (i < n) {
      dat[i] += x;
      i |= i + 1;
    }
  }
  int lower_bound(T x) {
    if (x < 0) return -1;
    int ret = -1;
    int k = 1;
    while (2 * k <= n) k <<= 1;
    for (; k > 0; k >>= 1) {
      if (ret + k < n && dat[ret + k] < x) {
        x -= dat[ret + k];
        ret += k;
      }
    }
    return ret + 1;
  }
};
int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(N + M), mn(N), mx(N);
  for (int i = 0; i < N; i++) A[N - 1 - i] = mn[i] = mx[i] = i;
  for (int i = 0; i < M; i++) {
    scanf("%d", &A[i + N]);
    A[i + N]--;
    mn[A[i + N]] = 0;
  }
  M += N;
  vector<vector<int>> pos(N);
  for (int i = 0; i < M; i++) pos[A[i]].push_back(i);
  vector<pair<int, int>> R2LI(M);
  for (int i = 0; i < N; i++) {
    int sz = pos[i].size();
    for (int j = 0; j < sz - 1; j++) R2LI[pos[i][j + 1]] = {pos[i][j], i};
  }
  BIT<int> bit(M);
  for (int r = N; r < M; r++) {
    int l = R2LI[r].first, i = R2LI[r].second;
    bit.plus(l, 1);
    int res = r - l - bit.sum_between(l, r);
    mx[i] = max(mx[i], res);
  }
  for (int i = 0; i < N; i++) {
    int l = pos[i].back(), r = M - 1;
    int res = r - l - bit.sum_between(l, r);
    mx[i] = max(mx[i], res);
  }
  for (int i = 0; i < N; i++) printf("%d %d\n", mn[i] + 1, mx[i] + 1);
  return 0;
}
