#include <bits/stdc++.h>
using namespace std;
inline void minimize(int &x, int y) { x = min(x, y); }
inline void maximize(int &x, int y) { x = max(x, y); }
const int N = 600000 + 1067, base = 1e9 + 7;
int n, m, top;
int block = 800;
int dem[N], a[N], l[N], r[N], bl[N], resa[N], resb[N], lst[N], type[N], pos[N];
bool comp(int c1, int c2) {
  return bl[l[c1]] < bl[l[c2]] || (bl[l[c1]] == bl[l[c2]] && r[c1] < r[c2]);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) a[i] = n - i + 1, resa[i] = i;
  for (int i = n + 1; i <= n + m; i++) {
    cin >> a[i];
    resa[a[i]] = 1;
  }
  m += n;
  for (int i = 1; i <= n; i++) lst[a[i]] = i;
  for (int i = n + 1; i <= m; i++) {
    ++top;
    l[top] = lst[a[i]] + 1;
    r[top] = i;
    lst[a[i]] = i;
    type[top] = a[i];
  }
  for (int i = 1; i <= n; i++) {
    ++top;
    l[top] = lst[i];
    r[top] = m;
    type[top] = i;
  }
  for (int i = 1; i <= top; i++) pos[i] = i;
  for (int i = 1; i <= m; i++) {
    bl[i] = i / block;
  }
  sort(pos + 1, pos + top + 1, comp);
  int curl, curr;
  curl = 1;
  curr = 1;
  dem[a[1]]++;
  int curres = 1;
  for (int i = 1; i <= top; i++) {
    int ll = l[pos[i]];
    int rr = r[pos[i]];
    while (curl > ll) {
      --curl;
      ++dem[a[curl]];
      if (dem[a[curl]] == 1) ++curres;
    }
    while (curl < ll) {
      --dem[a[curl]];
      if (dem[a[curl]] == 0) --curres;
      ++curl;
    }
    while (curr > rr) {
      --dem[a[curr]];
      if (dem[a[curr]] == 0) --curres;
      --curr;
    }
    while (curr < rr) {
      ++curr;
      ++dem[a[curr]];
      if (dem[a[curr]] == 1) ++curres;
    }
    maximize(resb[type[pos[i]]], curres);
  }
  for (int i = 1; i <= n; i++) cout << resa[i] << " " << resb[i] << endl;
}
