#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 6e5 + 10;
const int inf = 0x3f3f3f3f;
int d[maxn];
int lowbit(int x) { return x & (-x); }
void add(int pos, int x) {
  for (int i = pos; i < maxn; i += lowbit(i)) d[i] += x;
}
int query(int pos) {
  int ans = 0;
  for (int i = pos; i; i -= lowbit(i)) ans += d[i];
  return ans;
}
int pos[maxn];
int Max[maxn], Min[maxn];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int last = maxn - 1;
  int n, m;
  cin >> n >> m;
  for (int i = (n); i >= (1); i--) {
    pos[i] = last;
    add(last, 1);
    last--;
    Max[i] = Min[i] = i;
  }
  while (m--) {
    int x;
    cin >> x;
    Max[x] = max(Max[x], query(pos[x]));
    add(pos[x], -1);
    pos[x] = last--;
    add(pos[x], 1);
    Min[x] = 1;
  }
  for (int i = (1); i <= (n); i++) Max[i] = max(Max[i], query(pos[i]));
  for (int i = (1); i <= (n); i++) cout << Min[i] << ' ' << Max[i] << '\n';
  return 0;
}
