#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
vector<int> g[300005], order[300005];
int num[300005], l[300005], r[300005], cnt[300005] = {0}, bit[300005] = {0},
                                       app[300005] = {0}, out[300005];
int query(int index) {
  int ans = 0, i;
  for (i = index; i < 300005; i += (i & -i)) ans += bit[i];
  return ans;
}
void modify(int index) {
  int i;
  for (i = index; i; i -= (i & -i)) bit[i]++;
}
struct Q {
  int l, r, box, index;
} q[300005];
bool cmp(Q a, Q b) {
  if (a.box == b.box) return a.r < b.r;
  return a.box < b.box;
}
int main() {
  int i, j, n, m, id = 0, decomp;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= m; i++) {
    scanf("%d", &num[i]);
    g[num[i]].emplace_back(i);
  }
  decomp = sqrt(m);
  for (i = n; i >= 1; i--) l[i] = r[i] = i;
  for (i = 1; i <= m; i++) {
    l[num[i]] = 1;
    if (!cnt[num[i]]) {
      cnt[num[i]] = 1;
      r[num[i]] = max(r[num[i]], query(num[i] + 1) + num[i]);
      modify(num[i]);
    }
  }
  for (i = 1; i <= n; i++)
    if (!cnt[i]) r[i] = max(r[i], query(i + 1) + i);
  for (i = 1; i <= n; i++) {
    for (j = 0; j < (int)g[i].size() - 1; j++) {
      if (g[i][j + 1] - g[i][j] == 1) continue;
      q[id] = {g[i][j] + 1, g[i][j + 1] - 1, g[i][j] / decomp, id};
      order[i].emplace_back(id);
      id++;
    }
    if (g[i].size() && g[i][j] + 1 < m) {
      q[id] = {g[i][j] + 1, m, g[i][j] / decomp, id};
      order[i].emplace_back(id);
      id++;
    }
  }
  sort(q, q + id, cmp);
  int left = 0, right = -1, ans = 0;
  for (i = 0; i < id; i++) {
    while (right < q[i].r) {
      right++;
      if (!app[num[right]]) ans++;
      app[num[right]]++;
    }
    while (right > q[i].r) {
      app[num[right]]--;
      if (!app[num[right]]) ans--;
      right--;
    }
    while (left > q[i].l) {
      left--;
      if (!app[num[left]]) ans++;
      app[num[left]]++;
    }
    while (left < q[i].l) {
      app[num[left]]--;
      if (!app[num[left]]) ans--;
      left++;
    }
    out[q[i].index] = ans;
  }
  for (i = 1; i <= n; i++)
    for (auto x : order[i]) r[i] = max(r[i], out[x] + 1);
  for (i = 1; i <= n; i++) printf("%d %d\n", l[i], r[i]);
}
