#include <bits/stdc++.h>
using namespace std;
long long n, m, x;
long long a[1000005], fen[1000005];
;
pair<long long, long long> ans[1000005];
void update(long long p, long long val) {
  for (int i = p; i <= 1000005; i += i & -i) fen[i] += val;
}
long long sum(long long p) {
  long long ans = 0;
  for (int i = p; i; i -= i & -i) ans += fen[i];
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    a[n - i] = i + 1, update(i + 1, 1), ans[n - i] = {n - i, n - i};
  for (int i = 0; i < m; i++) {
    cin >> x;
    ans[x].second = max(n - sum(a[x]) + 1, ans[x].second);
    update(a[x], -1);
    a[x] = i + 1 + n;
    ans[x].first = 1;
    update(a[x], 1);
  }
  for (int i = 1; i <= n; i++) {
    ans[i].second = max(n - sum(a[i]) + 1, ans[i].second);
    cout << ans[i].first << " " << ans[i].second << endl;
  }
  return 0;
}
