#include <bits/stdc++.h>
using namespace std;
struct Node {
  int l, r;
} f[600010];
int n, m;
int a[300010];
int o[300010];
int c[300010];
int last[300010];
int l[300010];
int r[300010];
int ans[300010];
int c2[300010];
bool vis[300010];
vector<int> v[300010];
void add2(int x, int v) {
  for (int i = x; i <= n; i += i & (-i)) c2[i] += v;
}
int sum2(int x) {
  int ret = 0;
  for (int i = x; i; i -= i & (-i)) ret += c2[i];
  return ret;
}
void add(int x, int v) {
  for (int i = x; i <= m; i += i & (-i)) c[i] += v;
}
int sum(int x) {
  int ret = 0;
  for (int i = x; i; i -= i & (-i)) ret += c[i];
  return ret;
}
bool cmp(const int& x, const int& y) { return f[x].r < f[y].r; }
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d", &a[i]);
    v[a[i]].push_back(i);
  }
  for (int i = 1; i <= n; i++) r[i] = i;
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j < v[i].size(); j++) {
      if (v[i][j - 1] == v[i][j] - 1) continue;
      f[++cnt] = (Node){v[i][j - 1] + 1, v[i][j] - 1};
    }
    if (v[i].size() > 0 && v[i][v[i].size() - 1] + 1 <= m)
      f[++cnt] = (Node){v[i][v[i].size() - 1] + 1, m};
  }
  for (int i = 1; i <= cnt; i++) o[i] = i;
  sort(o + 1, o + cnt + 1, cmp);
  int cur = 1;
  for (int i = 1; i <= m; i++) {
    if (last[a[i]] > 0) add(last[a[i]], -1);
    add(i, 1);
    last[a[i]] = i;
    while (f[o[cur]].r == i) {
      ans[o[cur]] = sum(f[o[cur]].r) - sum(f[o[cur]].l - 1);
      cur++;
    }
  }
  for (int i = 1; i <= n; i++) l[i] = i;
  for (int i = 1; i <= m; i++) l[a[i]] = 1;
  for (int i = 1; i <= m; i++) {
    if (!vis[a[i]]) {
      r[a[i]] += sum2(n) - sum2(a[i]);
      vis[a[i]] = true;
      add2(a[i], 1);
    }
  }
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) r[i] += sum2(n) - sum2(i);
  }
  cnt = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j < v[i].size(); j++) {
      if (v[i][j - 1] == v[i][j] - 1) continue;
      r[i] = max(r[i], ans[++cnt] + 1);
    }
    if (v[i].size() && v[i][v[i].size() - 1] + 1 <= m)
      r[i] = max(r[i], ans[++cnt] + 1);
  }
  for (int i = 1; i <= n; i++) printf("%d %d\n", l[i], r[i]);
  return 0;
}
