#include <bits/stdc++.h>
using namespace std;
const int MAX = 6e5 + 10;
int n, m, a[MAX], mn[MAX], mx[MAX];
vector<int> v[MAX];
struct data {
  int l, r, idx;
  data() {}
  data(int _l, int _r, int _idx) {
    l = _l;
    r = _r;
    idx = _idx;
  }
};
int BLOCK_SIZE;
bool cmp(data a, data b) {
  if (a.l / BLOCK_SIZE != b.l / BLOCK_SIZE)
    return a.l / BLOCK_SIZE < b.l / BLOCK_SIZE;
  else if ((a.l / BLOCK_SIZE) & 1)
    return a.r < b.r;
  return a.r > b.r;
}
int cnt, q;
int freq[MAX];
data Q[MAX];
void add(int x) {
  freq[x]++;
  if (freq[x] == 1) cnt++;
}
void del(int x) {
  freq[x]--;
  if (freq[x] == 0) cnt--;
}
void MO() {
  BLOCK_SIZE = sqrt(m);
  sort(Q, Q + q, cmp);
  int st = 0, en = -1;
  for (int i = 0; i < q; i++) {
    int l = Q[i].l, r = Q[i].r, idx = Q[i].idx;
    while (en < r) {
      en++;
      add(a[en]);
    }
    while (en > r) {
      del(a[en]);
      en--;
    }
    while (st > l) {
      st--;
      add(a[st]);
    }
    while (st < l) {
      del(a[st]);
      st++;
    }
    mx[idx] = max(mx[idx], cnt + 1);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  m += n;
  for (int i = 0; i < m; i++) {
    if (i < n) {
      a[i] = n - i;
      mn[a[i]] = mx[a[i]] = n - i;
    } else {
      scanf("%d", &a[i]);
      mn[a[i]] = 1;
    }
    v[a[i]].push_back(i);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j < v[i].size(); j++) {
      int x = v[i][j - 1] + 1, y = v[i][j] - 1;
      Q[q].l = x;
      Q[q].r = y;
      Q[q++].idx = i;
    }
    if (v[i].back() < m - 1) {
      int x = v[i].back() + 1, y = m - 1;
      Q[q].l = x;
      Q[q].r = y;
      Q[q++].idx = i;
    }
  }
  MO();
  for (int i = 1; i <= n; i++) printf("%d %d\n", mn[i], mx[i]);
}
