#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m; cin >> n >> m;
    vector<int> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i];
        a[i]--;
    }
    vector<int>p(n);
    vector<int>pos(n);
    for (int i = 0; i < n; i++) {
        p[i] = i;
        pos[i] = i;
    }
    vector<int>p_min(n, 1000000000);
    vector<int>p_max(n, -1000000000);
    for (int i = 0; i < n; i++) {
        p_min[p[i]] = min(p_min[p[i]], i);
        p_max[p[i]] = max(p_max[p[i]], i);
    }
    for (int i = 0; i < m; i++) {
        if (pos[a[i]] != 0) {
            int l = p[pos[a[i]] - 1];
            int r = p[pos[a[i]]];
            swap(p[pos[a[i]] - 1], p[pos[a[i]]]);
            pos[l]++;
            pos[r]--;
            p_min[l] = min(p_min[l], pos[l]);
            p_max[l] = max(p_max[l], pos[l]);
            p_min[r] = min(p_min[r], pos[r]);
            p_max[r] = max(p_max[r], pos[r]);
        }
        /*
        for (int j = 0; j < n; j++) {
            cout << pos[j] << " ";
        }
        cout << endl;
        for (int j = 0; j < n; j++) {
            cout << p[j] << " ";
        }
        cout << endl;
        */
    }
    for (int i = 0; i < n; i++) {
        cout << p_min[i] + 1 << " " << p_max[i] + 1 << "\n";
    }
    return 0;
}