#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long powmod(long long a, long long b, long long MOD) {
  if (a == 0ll) {
    return 0ll;
  }
  a %= MOD;
  long long ans = 1;
  while (b) {
    if (b & 1) {
      ans = ans * a % MOD;
    }
    a = a * a % MOD;
    b >>= 1;
  }
  return ans;
}
void Pv(const vector<int>& V) {
  int Len = int(V.size());
  for (int i = 0; i < Len; ++i) {
    printf("%d", V[i]);
    if (i != Len - 1) {
      printf(" ");
    } else {
      printf("\n");
    }
  }
}
void Pvl(const vector<long long>& V) {
  int Len = int(V.size());
  for (int i = 0; i < Len; ++i) {
    printf("%lld", V[i]);
    if (i != Len - 1) {
      printf(" ");
    } else {
      printf("\n");
    }
  }
}
inline void getInt(int* p);
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
int n, m;
int a[maxn];
int tree[maxn];
int lowbit(int x) { return x & (-x); }
void add(int pos, int val) {
  while (pos < maxn) {
    tree[pos] += val;
    pos += lowbit(pos);
  }
}
int ask(int pos) {
  int res = 0;
  while (pos > 0) {
    res += tree[pos];
    pos -= lowbit(pos);
  }
  return res;
}
int be[maxn];
int ed[maxn];
int vis[maxn];
int main() {
  scanf("%d %d", &(n), &(m));
  for (int i = 1; i <= n; i++) {
    a[i] = n - i + 1;
  }
  for (int i = n + 1; i <= n + m; i++) {
    scanf("%d", &(a[i]));
    ;
    be[a[i]] = 1;
  }
  for (int i = 1; i <= n; i++) {
    if (!be[i]) {
      be[i] = i;
    }
  }
  for (int i = 1; i <= n + m; i++) {
    if (!vis[a[i]]) {
      add(i, 1);
    } else {
      add(vis[a[i]], -1);
      add(i, 1);
    }
    if (vis[a[i]]) ed[a[i]] = max(ed[a[i]], ask(i) - ask(vis[a[i]] - 1));
    vis[a[i]] = i;
  }
  for (int i = 1; i <= n; i++) {
    ed[i] = max(ed[i], ask(n + m) - ask(vis[i] - 1));
  }
  for (int i = 1; i <= n; i++) {
    printf("%d %d\n", be[i], ed[i]);
  }
  return 0;
}
inline void getInt(int* p) {
  char ch;
  do {
    ch = getchar();
  } while (ch == ' ' || ch == '\n');
  if (ch == '-') {
    *p = -(getchar() - '0');
    while ((ch = getchar()) >= '0' && ch <= '9') {
      *p = *p * 10 - ch + '0';
    }
  } else {
    *p = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9') {
      *p = *p * 10 + ch - '0';
    }
  }
}
