#include <bits/stdc++.h>
using namespace std;
const long long int MAX = 2e7 + 1;
long long int mod = 1e9 + 7;
vector<long long int> bit;
long long int tot;
void add(long long int pos, long long int val) {
  long long int i = pos;
  while (i <= tot) {
    bit[i] += val;
    i += (i & (-1 * i));
  }
}
long long int sum(long long int pos) {
  long long int x = 0;
  long long int i = pos;
  while (i > 0) {
    x += bit[i];
    i -= (i & -1 * (i));
  }
  return x;
}
void solve() {
  long long int n, m;
  cin >> n >> m;
  tot = n + m + 100;
  bit.resize(tot);
  vector<long long int> p(n + 1);
  vector<long long int> maxi(n + 1), mini(n + 1);
  for (long long int i = 1; i < n + 1; i++) {
    p[i] = i + m + 10;
    add(i + m + 10, 1);
    maxi[i] = i;
    mini[i] = i;
  }
  long long int str = p[1];
  for (long long int i = 0; i < m; i++) {
    long long int x;
    cin >> x;
    mini[x] = 1;
    maxi[x] = max(sum(p[x]), maxi[x]);
    add(p[x], -1);
    p[x] = str - 1;
    str = p[x];
    add(p[x], 1);
  }
  for (long long int i = 1; i < n + 1; i++) {
    maxi[i] = max(sum(p[i]), maxi[i]);
  }
  for (long long int i = 1; i < n + 1; i++)
    cout << mini[i] << ' ' << maxi[i] << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int t = 1;
  for (long long int i = 0; i < t; i++) {
    solve();
  }
}
