#include <bits/stdc++.h>
using namespace std;
char* get_new_c_string(const char* a, const char* b) {
  char* c_s = (char*)malloc((strlen(a) + strlen(b) + 1) * sizeof(char));
  strcpy(c_s, a);
  strcat(c_s, b);
  return c_s;
}
struct BinaryIndexedTree {
  unsigned int n;
  vector<int> a;
  BinaryIndexedTree(int n) {
    this->n = n;
    a.resize(this->n + 1);
  }
  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 main(int argc, char** argv) {
  int n, m, x;
  scanf("%d %d\n", &n, &m);
  vector<int> mx(n + 1, 0);
  vector<int> prev_q_pos(n + 1, 0);
  BinaryIndexedTree tree_n(n);
  BinaryIndexedTree tree_m(m);
  for (int i = 1; i <= m; ++i) {
    scanf("%d ", &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]));
    }
    printf("%d %d\n", min_pos, max_pos);
  }
  return 0;
}
