#include <bits/stdc++.h>
using namespace std;
const long long q = 239017;
const long long mod = 1e9 + 7;
const long long mod2 = 1e9 + 13;
const long long MAXN = 3e5 + 100;
const long long MAXM = 700;
const long long L = 26;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<long long> v[MAXM];
long long mx[MAXN], mn[MAXN], id[MAXN];
long long n, t;
vector<long long> orda;
void rebuild() {
  long long it = 1;
  if (orda.empty())
    for (long long i = 0; i < MAXM; ++i)
      for (long long j = 0; j < (long long)v[i].size(); ++j)
        orda.push_back(v[i][j]), mx[v[i][j]] = max(mx[v[i][j]], it++);
  for (long long i = 0; i < MAXM; ++i) v[i].clear();
  for (long long i = 0; i < n; ++i)
    v[i / MAXM].push_back(orda[i]), id[orda[i]] = i / MAXM;
  orda.clear();
}
void $main() {
  cin >> n >> t;
  orda.resize(n);
  for (long long i = 0; i < n; ++i) {
    orda[i] = i + 1;
    mx[i + 1] = mn[i + 1] = i + 1;
  }
  rebuild();
  long long rq = 0;
  while (t--) {
    long long cur;
    cin >> cur;
    long long it = 0;
    for (long long i = 0; i < id[cur]; ++i) it += (long long)v[i].size();
    for (long long i = 0; i < (long long)v[id[cur]].size(); ++i) {
      if (v[id[cur]][i] == cur) {
        mn[cur] = 1;
        mx[cur] = max(mx[cur], i + it + 1);
        v[id[cur]].erase(v[id[cur]].begin() + i);
        v[0].insert(v[0].begin(), cur);
        id[cur] = 0;
        break;
      }
    }
    ++rq;
    if (rq == MAXM) rebuild(), rq = 0;
  }
  rebuild();
  for (long long i = 1; i <= n; ++i) cout << mn[i] << " " << mx[i] << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  $main();
  return 0;
}
