#include <bits/stdc++.h>
using namespace std;
int l[300005], r[300005];
int tree[2 * 300005];
int n, m;
int pos[300005];
void add(int p, int val) {
  for (int i = p + 1; i <= n + m; i += i & (-i)) tree[i] += val;
}
int sum(int tar) {
  int ans = 0;
  for (int i = tar; i > 0; i -= i & (-i)) ans += tree[i];
  return ans;
}
int sum(int l, int r) { return sum(r) - sum(l); }
int main() {
  cin >> n >> m;
  for (int i = 0; i <= n; i++) l[i] = i, r[i] = i;
  for (int i = 0; i < n; i++) pos[i] = n - i - 1;
  for (int i = 0; i < n; i++) add(i, 1);
  for (int i = 0; i < m; i++) {
    int x;
    scanf("%d", &x);
    x--;
    l[x] = 0;
    r[x] = max(r[x], sum(pos[x] + 1, n + i));
    add(pos[x], -1);
    pos[x] = n + i;
    add(pos[x], 1);
  }
  for (int i = 0; i < n; i++) r[i] = max(r[i], sum(pos[i] + 1, n + m));
  for (int i = 0; i < n; i++) {
    printf("%d %d\n", l[i] + 1, r[i] + 1);
  }
}
