#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5 + 5;
struct BinaryIndexedTree {
  int a[MAX_N];
  int n;
  BinaryIndexedTree(int n) {
    this->n = n + 1;
    for (int i = 0; i <= this->n; ++i) {
      a[i] = 0;
    }
  }
  void update(int idx, int val) {
    for (int i = idx; i <= n; i += (i & (-i))) {
      a[i] += val;
    }
  }
  int query(int idx) {
    int sum = 0;
    for (int i = idx; i > 0; i -= (i & (-i))) {
      sum += a[i];
    }
    return sum;
  }
};
int n, m, x, mx[MAX_N];
int prev_q_pos[MAX_N];
int main(int argc, char** argv) {
  cin >> n >> m;
  BinaryIndexedTree tree_n(n);
  BinaryIndexedTree tree_m(m);
  for (int i = 1; i <= m; ++i) {
    cin >> x;
    tree_m.update(i, 1);
    if (!prev_q_pos[x]) {
      tree_n.update(x, 1);
      mx[x] = x + tree_n.query(n) - tree_n.query(x);
    } else {
      tree_m.update(prev_q_pos[x], -1);
      mx[x] = max(mx[x], tree_m.query(i) - tree_m.query(prev_q_pos[x]));
    }
    prev_q_pos[x] = i;
  }
  for (int i = 1; i <= n; ++i) {
    int min_pos = 0;
    int max_pos = 0;
    if (!prev_q_pos[i]) {
      min_pos = i;
      max_pos = i + tree_n.query(n) - tree_n.query(i);
    } else {
      min_pos = 1;
      max_pos = max(mx[i], tree_m.query(m) + 1 - tree_m.query(prev_q_pos[i]));
    }
    cout << min_pos << " " << max_pos << "\n";
  }
  return 0;
}
