#include <bits/stdc++.h>
namespace FastRead {
char __buff[5000];
int __lg = 0, __p = 0;
char nc() {
  if (__lg == __p) {
    __lg = fread(__buff, 1, 5000, stdin);
    __p = 0;
    if (!__lg) return EOF;
  }
  return __buff[__p++];
}
template <class T>
void read(T& __x) {
  T __sgn = 1;
  char __c;
  while (!isdigit(__c = nc()))
    if (__c == '-') __sgn = -1;
  __x = __c - '0';
  while (isdigit(__c = nc())) __x = __x * 10 + __c - '0';
  __x *= __sgn;
}
}  // namespace FastRead
using namespace FastRead;
using namespace std;
const int N = 3e5 + 10;
const int M = 1e9 + 7;
const long double PI = acos(-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m;
int a[N], bit[2 * N], pos[N], mn[N], mx[N];
void upd(int x, int val) {
  for (; x <= n + m; x += x & -x) bit[x] += val;
}
int get(int x) {
  int ans = 0;
  for (; x; x -= x & -x) ans += bit[x];
  return ans;
}
signed main() {
  int i;
  cin >> n >> m;
  for (i = 1; i <= n; i++) mn[i] = i, pos[i] = n + 1 - i, upd(pos[i], 1);
  for (i = 1; i <= m; i++) {
    cin >> a[i];
    mn[a[i]] = 1;
    mx[a[i]] = max(mx[a[i]], n + 1 - get(pos[a[i]]));
    upd(pos[a[i]], -1);
    pos[a[i]] = i + n;
    upd(pos[a[i]], 1);
  }
  for (i = 1; i <= n; i++) mx[i] = max(mx[i], n + 1 - get(pos[i]));
  for (i = 1; i <= n; i++) cout << mn[i] << ' ' << mx[i] << '\n';
  return 0;
}
