#include <bits/stdc++.h>
using namespace std;
const int MAX = 3e5 + 10;
struct FenwickTree {
  int n;
  vector<long long> BIT;
  FenwickTree(int n) : n(n), BIT(2 * n) {}
  void update(int x, long long val) {
    while (x < n) {
      BIT[x] += val;
      x |= x + 1;
    }
  }
  long long get(int x) {
    long long sum = 0;
    while (x > 0) {
      sum += BIT[x];
      x = (x & (x + 1)) - 1;
    }
    return sum;
  }
};
int p[MAX], mn[MAX], mx[MAX], a[MAX];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  FenwickTree fw(n + m);
  for (int i = 0; i < n; i++) {
    mn[i] = mx[i] = i;
    p[i] = i + m;
  }
  for (int i = 0; i < m; i++) {
    cin >> a[i];
    a[i]--;
    mn[a[i]] = 0;
  }
  for (int i = 0; i < n; i++) {
    fw.update(p[i], 1);
  }
  for (int i = 0; i < m; i++) {
    int x = a[i];
    mx[x] = max((long long)mx[x], fw.get(p[x]) - 1);
    fw.update(p[x], -1);
    p[x] = m - i - 1;
    fw.update(p[x], 1);
  }
  for (int i = 0; i < n; i++) {
    mx[i] = max((long long)mx[i], fw.get(p[i]) - 1);
    cout << mn[i] + 1 << " " << mx[i] + 1 << "\n";
  }
  return 0;
}
