#include <bits/stdc++.h>
using namespace std;
int n, m;
int v[300000 + 1];
int mx[300000 + 1];
int mn[300000 + 1];
int last[300000 + 1];
int aib[300000 + 1][2];
void readFile() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) mn[i] = mx[i] = i;
  for (int i = 1; i <= m; i++) {
    cin >> v[i];
    mn[v[i]] = 1;
  }
}
void upd(int cr, int poz, int nr) {
  int lim = (cr == 0 ? n : m);
  while (poz <= lim) {
    aib[poz][cr] += nr;
    poz += poz & (-poz);
  }
}
int getSum(int cr, int poz) {
  int rez = 0;
  while (poz >= 1) {
    rez += aib[poz][cr];
    poz -= poz & (-poz);
  }
  return rez;
}
void solve() {
  for (int i = 1; i <= m; i++) {
    int pcr = 0;
    if (last[v[i]] == 0) {
      pcr = v[i] + getSum(0, n);
      pcr -= getSum(0, v[i]);
    } else {
      pcr = 1 + getSum(1, i - 1);
      pcr -= getSum(1, last[v[i]]);
    }
    mx[v[i]] = max(mx[v[i]], pcr);
    if (last[v[i]] == 0)
      upd(0, v[i], 1);
    else
      upd(1, last[v[i]], -1);
    last[v[i]] = i;
    upd(1, i, 1);
  }
  for (int i = 1; i <= n; i++) {
    int pcr = 0;
    if (last[i] == 0) {
      pcr = i + getSum(0, n);
      pcr -= getSum(0, i);
    } else {
      pcr = 1 + getSum(1, m);
      pcr -= getSum(1, last[i]);
    }
    mx[i] = max(mx[i], pcr);
  }
}
void printFile() {
  for (int i = 1; i <= n; i++) cout << mn[i] << " " << mx[i] << "\n";
}
int main() {
  readFile();
  solve();
  printFile();
  return 0;
}
