#include <bits/stdc++.h>
using namespace std;
struct BitTree {
  vector<int> sum;
  void update(int id, int delta) {
    if (id >= sum.size()) return;
    sum[id] += delta;
    update(id | (id + 1), delta);
  }
  int getSum(int id) {
    return id == -1 ? 0 : sum[id] + getSum((id & (id + 1)) - 1);
  }
  void create(vector<int> &a) {
    sum.resize(a.size());
    for (int i = 0; i < a.size(); i++) update(i, a[i]);
  }
};
int main() {
  iostream::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<int> a(m);
  for (int &a1 : a) cin >> a1;
  vector<int> pos(m), id(n + 1), mn(n + 1), mx(n + 1);
  for (int i = 1; i <= n; i++) id[i] = pos.size(), pos.push_back(1);
  BitTree b;
  b.create(pos);
  pos.clear();
  for (int i = 1; i <= n; i++) mn[i] = i;
  int t = a.size() - 1;
  for (int a1 : a) {
    mn[a1] = 1;
    mx[a1] = max(b.getSum(id[a1]), mx[a1]);
    b.update(id[a1], -1);
    id[a1] = t--;
    b.update(id[a1], 1);
  }
  for (int i = 1; i <= n; i++)
    cout << mn[i] << ' ' << max(b.getSum(id[i]), mx[i]) << '\n';
}
