#include <bits/stdc++.h>
using namespace std;
int n, m;
const int MAX = 600000;
int bit[600000 + 10];
int pos[300010];
int mn[300010], mx[300010];
void update(int x, int val) {
  for (; x <= MAX; x += x & (-x)) bit[x] += val;
}
int query(int x) {
  int ret = 0;
  for (; x; x -= (x & (-x))) ret += bit[x];
  return ret;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    pos[i] = MAX - (n - i);
    update(MAX - (n - i), 1);
    mn[i] = mx[i] = i;
  }
  int now = MAX - n;
  for (int i = 1; i <= m; i++) {
    int x;
    scanf("%d", &x);
    mx[x] = max(mx[x], query(pos[x]));
    mn[x] = 1;
    update(pos[x], -1);
    update(now, 1);
    pos[x] = now--;
  }
  for (int i = 1; i <= n; i++)
    mx[i] = max(mx[i], query(pos[i])), printf("%d %d\n", mn[i], mx[i]);
  return 0;
}
