#include <bits/stdc++.h>
using namespace std;
const long long MaxN = 1e6 + 100;
const long long LogN = 20;
long long Inf = 1e18;
const long long dx[4] = {0, 1, 0, -1};
const long long dy[4] = {1, 0, -1, 0};
long long Tree[MaxN];
void upd(int i, long long k = 1) {
  for (; i < MaxN; i = (i | (i + 1))) Tree[i] += k;
}
long long get(int r) {
  int result = 0;
  for (; r >= 0; r = (r & (r + 1)) - 1) result += Tree[r];
  return result;
}
long long Mt[MaxN];
pair<long long, long long> Ans[MaxN];
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long N, K;
  cin >> N >> K;
  for (int i = K; i < K + N; i++) {
    upd(i);
    Mt[i - K] = i;
    Ans[i - K].second = Ans[i - K].first = i - K + 1;
  }
  while (K--) {
    long long x;
    cin >> x;
    x--;
    long long t = x;
    x = Mt[x];
    Ans[t].first = 1;
    long long k = get(x);
    Ans[t].second = max(Ans[t].second, k);
    upd(x, -1);
    upd(K);
    Mt[t] = K;
  }
  for (int i = 0; i < N; i++) {
    Ans[i].second = max(get(Mt[i]), Ans[i].second);
    cout << Ans[i].first;
    cout << ' ';
    cout << Ans[i].second;
    cout << '\n';
  }
  return 0;
}
