#include <bits/stdc++.h>
const int maxn = 300005;
using namespace std;
class FenwickTree {
 public:
  void set(int n) {
    data.resize(n + 1);
    len = n;
  }
  void modify(int p, int det) { _modify(p, det); }
  int query_sum(int l, int r) { return _query(r) - _query(l - 1); }

 private:
  vector<int> data;
  int len;
  void _modify(int p, int det) {
    while (p <= len) {
      data[p] += det;
      p += p & -p;
    }
  }
  int _query(int l) {
    int result = 0;
    while (l != 0) {
      result += data[l];
      l ^= l & -l;
    }
    return result;
  }
};
int n, m;
int mi_pos[maxn], ma_pos[maxn], last_seen[maxn];
FenwickTree pos, is_seen;
void run() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  pos.set(m);
  is_seen.set(n);
  for (int i = 1; i <= n; ++i) {
    mi_pos[i] = ma_pos[i] = i;
    last_seen[i] = -1;
  }
  for (int i = 1; i <= m; ++i) {
    int x = 0;
    cin >> x;
    if (last_seen[x] == -1) {
      ma_pos[x] = max(ma_pos[x], x + is_seen.query_sum(x + 1, n));
      is_seen.modify(x, 1);
      pos.modify(i, 1);
    } else {
      ma_pos[x] = max(ma_pos[x], pos.query_sum(last_seen[x] + 1, i) + 1);
      pos.modify(last_seen[x], -1);
      pos.modify(i, 1);
    }
    last_seen[x] = i;
    mi_pos[x] = 1;
  }
  for (int x = 1; x <= n; ++x) {
    if (last_seen[x] == -1) {
      ma_pos[x] = max(ma_pos[x], x + is_seen.query_sum(x + 1, n));
    } else {
      ma_pos[x] = max(ma_pos[x], pos.query_sum(last_seen[x] + 1, m) + 1);
    }
  }
  for (int i = 1; i <= n; ++i) {
    cout << mi_pos[i] << " " << ma_pos[i] << "\n";
  }
}
int main() {
  run();
  return 0;
}
