#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 9;
const long long mod = 1e9 + 7;
int sum[N], sum2[N];
void Set(int p, int val) {
  for (int i = p; i < N; i += ((i) & (-i))) sum[i] += val;
}
int Get(int p) {
  int res = 0;
  for (int i = p; i; i ^= ((i) & (-i))) res += sum[i];
  return res;
}
void Set2(int p, int val) {
  for (int i = p; i < N; i += ((i) & (-i))) sum2[i] += val;
}
int Get2(int p) {
  int res = 0;
  for (int i = p; i; i ^= ((i) & (-i))) res += sum2[i];
  return res;
}
int mini[N], maxn[N], flag[N], a[N], last[N];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = (1); i < (n + 1); ++i) mini[i] = maxn[i] = i;
  for (int i = (1); i < (m + 1); ++i) {
    scanf("%d", &a[i]);
    if (!last[a[i]]) {
      Set(a[i], 1);
      Set2(i, 1);
      maxn[a[i]] = max(maxn[a[i]], a[i] + Get(n) - Get(a[i]));
    } else {
      Set2(i, 1);
      Set2(last[a[i]], -1);
      maxn[a[i]] = max(maxn[a[i]], Get2(i) - Get2(last[a[i]]));
    }
    last[a[i]] = i;
    mini[a[i]] = 1;
  }
  Set2(m + 1, 1);
  for (int i = (1); i < (n + 1); ++i) {
    if (!last[i]) {
      maxn[i] = max(maxn[i], i + Get(n) - Get(i));
    } else {
      maxn[i] = max(maxn[i], Get2(m + 1) - Get2(last[i]));
    }
    printf("%d %d\n", mini[i], maxn[i]);
  }
}
