#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
long long inf = 1LL << 50;
const int N = 300000;
struct segTreeSum {
  int* tree;
  int len;
  vector<int> input;
  segTreeSum(vector<int>& input, int l) {
    tree = new int[2 * (int)pow(2, ceil(log2(l))) - 1];
    len = l;
    this->input = input;
    constructTree(0, len - 1, 0);
  }
  void constructTree(int low, int high, int pos) {
    if (low == high) {
      tree[pos] = input[low];
      return;
    }
    int mid = (low + high) / 2;
    constructTree(low, mid, pos * 2 + 1);
    constructTree(mid + 1, high, pos * 2 + 2);
    tree[pos] = tree[pos * 2 + 2] + tree[pos * 2 + 1];
  }
  int query(int low, int high) { return rangeSum(low, high, 0, len - 1, 0); }
  int rangeSum(int qlow, int qhigh, int low, int high, int pos) {
    if (qlow <= low && qhigh >= high) {
      return tree[pos];
    }
    if (qlow > high || low > qhigh) {
      return 0;
    }
    int mid = (low + high) / 2;
    return rangeSum(qlow, qhigh, low, mid, pos * 2 + 1) +
           rangeSum(qlow, qhigh, mid + 1, high, pos * 2 + 2);
  }
  void update(int pos, int newVal) {
    update(pos, newVal - input[pos], 0, len - 1, 0);
    input[pos] = newVal;
  }
  void update(int i, int diff, int low, int high, int pos) {
    if (i > high || low > i) {
      return;
    }
    tree[pos] += diff;
    if (low != high) {
      int mid = (low + high) / 2;
      update(i, diff, low, mid, pos * 2 + 1);
      update(i, diff, mid + 1, high, pos * 2 + 2);
    }
  }
  int search(int low, int high, int pos, int val) {
    if (low == high) {
      return low;
    }
    int mid = (low + high) / 2;
    if (tree[pos * 2 + 1] >= val) {
      return search(low, mid, pos * 2 + 1, val);
    }
    return search(mid + 1, high, pos * 2 + 2, val - tree[pos * 2 + 1]);
  }
};
pair<int, int> ans[N + 5];
int q[N + 5];
int pos[N + 5];
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin.exceptions(cin.failbit);
  int n, m;
  cin >> n >> m;
  vector<int> input(n + m, 0);
  for (int i = 0; i < m; i++) {
    cin >> q[i];
    q[i]--;
  }
  for (int i = 0; i < n; i++) {
    input[i + m] = 1;
    ans[i].first = i;
    ans[i].second = i;
    pos[i] = i + m;
  }
  segTreeSum st(input, n + m);
  for (int i = 0; i < m; i++) {
    st.update(pos[q[i]], 0);
    ans[q[i]].second = max(ans[q[i]].second, st.query(0, pos[q[i]]));
    pos[q[i]] = m - i - 1;
    st.update(pos[q[i]], 1);
    ans[q[i]].first = 0;
  }
  for (int i = 0; i < n; i++) {
    ans[i].second = max(ans[i].second, st.query(0, pos[i]) - 1);
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i].first + 1 << " " << ans[i].second + 1 << "\n";
  }
}
