#include <bits/stdc++.h>
using namespace std;
template <class U, class V>
ostream &operator<<(ostream &os, pair<U, V> p) {
  return os << p.first << " " << p.second;
}
template <class U, class V>
istream &operator>>(istream &is, pair<U, V> &p) {
  return is >> p.first >> p.second;
}
const int N = 1000006;
int f[N];
int sum(int r) {
  int res = 0;
  for (; r >= 0; r = (r & (r + 1)) - 1) res += f[r];
  return res;
}
int sum(int l, int r) { return sum(r) - sum(l - 1); }
void add(int x, int delta) {
  for (; x < N; x |= x + 1) f[x] += delta;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> v(n + m);
  for (int i = 0; i < n; i++) v[i] = n - 1 - i;
  vector<int> used(n);
  for (int i = 0; i < m; i++) {
    cin >> v[n + i];
    v[n + i]--;
    used[v[n + i]] = 1;
  }
  vector<int> lst(n, n + m);
  vector<int> res(n);
  for (int i = n + m - 1; i >= 0; i--) {
    res[v[i]] = max(res[v[i]], sum(i + 1, lst[v[i]] - 1));
    if (lst[v[i]] != n + m) add(lst[v[i]], -1);
    lst[v[i]] = i;
    add(i, 1);
  }
  for (int i = 0; i < n; i++) {
    if (!used[i])
      cout << i + 1 << " ";
    else
      cout << 1 << " ";
    cout << res[i] + 1 << "\n";
  }
}
