#include <bits/stdc++.h>
using namespace std;
struct STree {
  int l, r;
  int sum = 0;
  STree* left = 0;
  STree* right = 0;
  STree(vector<int>& arr, int l, int r) : l(l), r(r) {
    if (l == r) {
      sum = arr[l];
      return;
    }
    int m = (l + r) >> 1;
    left = new STree(arr, l, m);
    right = new STree(arr, m + 1, r);
    sum = left->sum + right->sum;
  }
  void update(const int pos, const int val) {
    if (not(l <= pos and pos <= r)) return;
    if (l == pos and pos == r) {
      sum = val;
      return;
    }
    left->update(pos, val);
    right->update(pos, val);
    sum = left->sum + right->sum;
  }
  int get(const int L, const int R) {
    if (R < l or r < L) return 0;
    if (L <= l and r <= R) return sum;
    return left->get(L, R) + right->get(L, R);
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(m);
  for (int& ai : a) cin >> ai;
  set<int> sa(begin(a), end(a));
  vector<int> ft(n + 10, 0);
  auto get = [&](int pos) {
    int ret = 0;
    while (pos) {
      ret += ft[pos];
      pos -= pos & -pos;
    }
    return ret;
  };
  auto update = [&](int pos, int var) {
    while (pos < int(ft.size())) {
      ft[pos] += var;
      pos += pos & -pos;
    }
  };
  auto sum = [&](int l, int r) {
    if (l > r) return 0;
    return get(r) - get(l - 1);
  };
  vector<vector<int>> pos(n + 1);
  vector<int> mx(n + 1);
  iota(begin(mx), end(mx), 0);
  vector<pair<pair<int, int>, int>> query;
  vector<int> nxt(m, -1);
  for (int i = 0; i < m; i++) {
    pos[a[i]].push_back(i);
    if (int(pos[a[i]].size()) == 1) {
      mx[a[i]] = max(mx[a[i]], a[i] + sum(a[i] + 1, n));
    } else {
      int l = end(pos[a[i]])[-2];
      int r = end(pos[a[i]])[-1];
      nxt[l] = r;
      if (l + 1 != r) {
        query.push_back(make_pair(pair<int, int>(l + 1, r - 1), a[i]));
      }
    }
    if (sum(a[i], a[i]) == 0) {
      update(a[i], 1);
    }
  }
  set<int> vis;
  vector<bool> used(n + 1, false);
  for (int i = m - 1; i >= 0; i--) {
    if (not used[a[i]]) {
      mx[a[i]] = max(mx[a[i]], 1 + int(vis.size()));
    }
    used[a[i]] = true;
    vis.insert(a[i]);
  }
  vector<int> arr(m, 0);
  for (int i = 1; i <= n; i++) {
    if (not pos[i].empty()) {
      arr[pos[i][0]] = 1;
    }
  }
  sort(begin(query), end(query));
  STree tree(arr, 0, m - 1);
  int cur = 0;
  for (auto qq : query) {
    int l = qq.first.first;
    int r = qq.first.second;
    int ai = qq.second;
    while (cur < l) {
      tree.update(cur, 0);
      if (nxt[cur] != -1) tree.update(nxt[cur], 1);
      cur++;
    }
    mx[ai] = max(mx[ai], 1 + tree.get(l, r));
  }
  for (int i = 1; i <= n; i++) {
    int mn = i;
    if (sa.count(i)) mn = 1;
    if (pos[i].empty()) {
      mx[i] = max(mx[i], i + sum(i + 1, n));
    }
    cout << mn << ' ' << mx[i] << '\n';
  }
  return (0);
}
