#include <bits/stdc++.h>
using namespace std;
struct Fenwick {
  int n;
  vector<int> tree;
  Fenwick(int n_) : n(n_), tree(n + 1) {}
  int lsb(int x) { return x & -x; }
  void Update(int pos, int val) {
    for (pos = n - pos; pos <= n; pos += lsb(pos)) tree[pos] += val;
  }
  int Query(int pos) {
    int ans = 0;
    for (pos = n - pos; pos; pos -= lsb(pos)) ans += tree[pos];
    return ans;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n, m;
  cin >> n >> m;
  Fenwick fw(n + m);
  vector<int> last(n), lft(n), rgt(n);
  for (int i = 0; i < n; ++i) {
    fw.Update(i, 1);
    lft[i] = rgt[i] = i + 1;
    last[i] = n - i - 1;
  }
  for (int i = 0; i < m; ++i) {
    int x;
    cin >> x;
    --x;
    fw.Update(last[x], -1);
    lft[x] = 1;
    rgt[x] = max(rgt[x], fw.Query(last[x]) + 1);
    fw.Update(i + n, +1);
    last[x] = i + n;
  }
  for (int i = 0; i < n; ++i) {
    rgt[i] = max(rgt[i], fw.Query(last[i]));
  }
  for (int i = 0; i < n; ++i) {
    cout << lft[i] << ' ' << rgt[i] << '\n';
  }
}
