#include <bits/stdc++.h>
using namespace std;
class DebugStream {
} LOG;
template <typename T>
DebugStream &operator<<(DebugStream &s, const T &) {
  return s;
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 3e5 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 335, lg = 20,
          bs = 29;
int n, m, arr[2 * maxN], buc[maxN], dif;
vector<int> inds[maxN];
inline void remove(int idx) {
  if (!--buc[arr[idx]]) dif--;
}
inline void add(int idx) {
  if (!buc[arr[idx]]++) dif++;
}
int block_size = 700;
struct Query {
  int l, r, idx;
  bool operator<(Query other) const {
    return make_pair(l / block_size, r) <
           make_pair(other.l / block_size, other.r);
  }
};
vector<int> mo_s_algorithm(vector<Query> queries) {
  vector<int> answers(n + 1);
  sort(queries.begin(), queries.end());
  int cur_l = 0;
  int cur_r = -1;
  for (Query &q : queries) {
    while (cur_l > q.l) {
      cur_l--;
      add(cur_l);
    }
    while (cur_r < q.r) {
      cur_r++;
      add(cur_r);
    }
    while (cur_l < q.l) {
      remove(cur_l);
      cur_l++;
    }
    while (cur_r > q.r) {
      remove(cur_r);
      cur_r--;
    }
    answers[q.idx] = max(answers[q.idx], dif + 1);
  }
  return answers;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    arr[i + 1] = n - i;
  }
  for (int i = 0; i < m; i++) {
    cin >> arr[1 + n + i];
  }
  for (int i = 1; i <= n + m; i++) {
    inds[arr[i]].push_back(i);
  }
  for (int i = 1; i <= n; i++) inds[i].push_back(n + m + 1);
  vector<Query> qrs;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j < inds[i].size(); j++)
      qrs.push_back({inds[i][j - 1] + 1, inds[i][j] - 1, i});
  auto anss = mo_s_algorithm(qrs);
  for (int i = 1; i <= n; i++) {
    if (inds[i].size() > 2)
      cout << "1 ";
    else
      cout << i << ' ';
    cout << anss[i] << '\n';
  }
}
