#include <bits/stdc++.h>
using namespace std;
template <typename T>
string tos(T a) {
  stringstream ss;
  string ret;
  ss << a;
  ss >> ret;
  return ret;
}
void read(int &_a) { int temp = scanf("%d", &_a); }
void read(int &_a, int &_b) { int temp = scanf("%d %d", &_a, &_b); }
void read(int &_a, int &_b, int &_c) {
  int temp = scanf("%d %d %d", &_a, &_b, &_c);
}
const int SZ = 3e5 + 2;
int N, M, AR[SZ], FR[2 * SZ], MN[SZ], MX[SZ], LOC[2 * SZ];
void addc(int idx, int v) {
  if (idx < 1) return;
  int mx = 2 * SZ;
  while (idx < mx) {
    FR[idx] += v;
    idx += (idx & -idx);
  }
}
void addr(int L, int R, int v) {
  addc(L, v);
  addc(R + 1, -v);
}
int get(int idx) {
  if (idx < 1) return 0;
  int sum = 0;
  while (idx > 0) {
    sum += FR[idx];
    idx -= (idx & -idx);
  }
  return sum;
}
int main() {
  while (cin >> N >> M) {
    memset(FR, 0, sizeof FR);
    ;
    int head = SZ;
    for (int(p) = (1); (p) < (N + 1); (p)++) {
      MN[p] = MX[p] = p;
      LOC[p] = SZ + p - 1;
      addc(SZ + p, 1);
    }
    for (int(x) = (0); (x) < (M); (x)++) {
      int p;
      read(p);
      MN[p] = 1;
      int loc = LOC[p];
      int pos = get(loc);
      MX[p] = max(MX[p], pos + 1);
      LOC[p] = --head;
      addr(head + 1, loc, 1);
    }
    for (int(p) = (1); (p) < (N + 1); (p)++) {
      int loc = LOC[p];
      int pos = get(loc);
      MX[p] = max(MX[p], pos + 1);
      printf("%d %d\n", MN[p], MX[p]);
    }
  }
  return 0;
}
