#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 5;
int ans1[N], ans2[N], a[N * 2], tot, vis[N];
vector<int> g[N];
struct Node {
  int l, r, id, Bod;
} node[N];
int cmp(Node a, Node b) {
  if (a.Bod == b.Bod)
    return a.r < b.r;
  else
    return a.Bod < b.Bod;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int N = n + m;
  int B = sqrt(N);
  for (int i = 1; i <= n; i++) a[i] = n - i + 1, ans1[i] = i;
  for (int i = n + 1; i <= n + m; i++) scanf("%d", &a[i]), ans1[a[i]] = 1;
  for (int i = 1; i <= N; i++) g[a[i]].push_back(i);
  int qn = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < g[i].size(); j++) {
      if (j == g[i].size() - 1)
        node[tot++] = Node{g[i][j], N, i, (g[i][j] - 1) / B + 1};
      else
        node[tot++] = Node{g[i][j], g[i][j + 1], i, (g[i][j] - 1) / B + 1};
    }
  }
  sort(node, node + tot, cmp);
  int l = 1, r = 1, ans = 1;
  vis[a[1]] = 1;
  for (int i = 0; i < tot; i++) {
    while (r < node[i].r) {
      r++;
      vis[a[r]]++;
      if (vis[a[r]] == 1) ans++;
    }
    while (l > node[i].l) {
      l--;
      vis[a[l]]++;
      if (vis[a[l]] == 1) ans++;
    }
    while (r > node[i].r) {
      vis[a[r]]--;
      if (vis[a[r]] == 0) ans--;
      r--;
    }
    while (l < node[i].l) {
      vis[a[l]]--;
      if (!vis[a[l]]) ans--;
      l++;
    }
    ans2[node[i].id] = max(ans2[node[i].id], ans);
  }
  for (int i = 1; i <= n; i++) printf("%d %d\n", ans1[i], ans2[i]);
  return 0;
}
