#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 40;
const int BLSZ = 557;
int mn[MAXN], over[MAXN], n, m;
deque<int> no[MAXN / BLSZ + 1];
int where[MAXN];
void solve() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    mn[i] = over[i] = i + 1;
    no[i / BLSZ].push_back(i);
    where[i] = i / BLSZ;
  }
  for (int i = 0; i < m; ++i) {
    int cur;
    cin >> cur;
    cur--;
    mn[cur] = 1;
    int id = -1;
    int num = where[cur];
    for (int j = 0; j < no[num].size(); ++j) {
      if (no[num][j] == cur) {
        id = j;
        break;
      }
    }
    over[cur] = max(over[cur], (num * BLSZ) + id + 1);
    no[num].erase(no[num].begin() + id);
    where[cur] = 0;
    no[0].push_front(cur);
    for (int j = 0; j + 1 <= num; ++j) {
      int k = no[j].back();
      where[k]++;
      no[j].pop_back();
      no[j + 1].push_front(k);
    }
  }
  vector<int> kafka;
  for (int i = 0; i <= (n - 1) / BLSZ; ++i) {
    for (int j : no[i]) {
      kafka.push_back(j);
    }
  }
  for (int i = 0; i < n; ++i) {
    over[kafka[i]] = max(over[kafka[i]], i + 1);
  }
  for (int i = 0; i < n; ++i) {
    cout << mn[i] << " " << over[i] << "\n";
  }
}
int main() {
  ios::sync_with_stdio(false);
  solve();
  return 0;
}
