#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long n, m, len;
vector<long long> mx, mn, bpos;
vector<deque<long long>> b;
void to_front(long long x) {
  long long pos =
      find(b[bpos[x]].begin(), b[bpos[x]].end(), x) - b[bpos[x]].begin();
  mx[x] = max(mx[x], bpos[x] * len + pos);
  mn[x] = 0;
  b[bpos[x]].erase(b[bpos[x]].begin() + pos);
  for (long long i = 0; i < bpos[x]; i++) {
    bpos[b[i].back()]++;
    b[i + 1].push_front(b[i].back());
    b[i].pop_back();
  }
  bpos[x] = 0;
  b[0].push_front(x);
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  len = sqrt(n);
  b.resize((n + len - 1) / len);
  bpos.resize(n);
  mn.resize(n);
  mx.resize(n);
  for (long long i = 0; i < n; i++) {
    bpos[i] = i / len;
    mn[i] = mx[i] = i;
    b[bpos[i]].push_back(i);
  }
  long long cnt = 0;
  for (long long i = 0; i < m; i++) {
    long long x;
    cin >> x;
    to_front(x - 1);
  }
  for (auto i : b) {
    long long pos = -1;
    for (auto x : i) {
      mx[x] = max(mx[x], bpos[x] * len + ++pos);
    }
  }
  for (long long i = 0; i < n; i++) {
    cout << mn[i] + 1 << " ";
    cout << mx[i] + 1 << "\n";
  }
  return 0;
}
