#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
int t[maxn * 2];
int ansMin[maxn + 1], ansMax[maxn + 1];
int n, m;
inline int lowbit(int x) { return x & (-x); }
void add(int x, int k) {
  while (x <= n + m) {
    t[x] = t[x] + k;
    x += lowbit(x);
  }
}
int get(int x) {
  int ans = 0;
  while (x >= 1) {
    ans += t[x];
    x -= lowbit(x);
  }
  return ans;
}
int main() {
  scanf("%d%d", &n, &m);
  int pos[n + m + 1];
  for (int i = 1; i <= n; i++) {
    pos[i] = i + m;
    ansMin[i] = i, ansMax[i] = i;
    add(i + m, 1);
  }
  for (int i = 0; i < m; i++) {
    int temp;
    scanf("%d", &temp);
    ansMin[temp] = 1;
    add(pos[temp], -1);
    add(m - i, 1);
    ansMax[temp] = max(ansMax[temp], get(pos[temp]));
    pos[temp] = m - i;
  }
  for (int i = 1; i <= n; i++) {
    ansMax[i] = max(ansMax[i], get(pos[i]));
  }
  for (int i = 1; i <= n; i++) {
    printf("%d %d\n", ansMin[i], ansMax[i]);
  }
  return 0;
}
