#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
int a[N], minv[N], maxv[N], cnt[N];
int n, m;
int tr[N * 2];
map<int, int> mp;
int lowbit(int x) { return x & -x; }
void add(int x, int c) {
  for (int i = x; i <= n + m; i += lowbit(i)) tr[i] += c;
}
int sum(int x) {
  int res = 0;
  for (int i = x; i; i -= lowbit(i)) res += tr[i];
  return res;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d", &a[i]);
    cnt[a[i]]++;
  }
  for (int i = 1; i <= n; i++) {
    if (cnt[i])
      minv[i] = 1;
    else
      minv[i] = i;
    maxv[i] = i;
    mp[i] = m + i;
    add(m + i, 1);
  }
  for (int i = 1; i <= m; i++) {
    maxv[a[i]] = max(maxv[a[i]], sum(mp[a[i]]));
    add(mp[a[i]], -1);
    mp[a[i]] = m - i + 1;
    add(mp[a[i]], +1);
  }
  for (int i = 1; i <= n; i++) maxv[i] = max(maxv[i], sum(mp[i]));
  for (int i = 1; i <= n; i++) printf("%d %d\n", minv[i], maxv[i]);
  return 0;
}
