#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("-ffloat-store")
using namespace std;
clock_t time_p = clock();
void aryanc403() {}
const int INF = 0xFFFFFFFFFFFFFFFL;
int seed;
mt19937 rng(seed = chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l = 0, int r = INF) {
  return uniform_int_distribution<int>(l, r)(rng);
}
class CMP {
 public:
  bool operator()(pair<int, int> a, pair<int, int> b) {
    return !(a.first < b.first || (a.first == b.first && a.second <= b.second));
  }
};
void add(map<int, int> &m, int x, int cnt = 1) {
  auto jt = m.find(x);
  if (jt == m.end())
    m.insert({x, cnt});
  else
    jt->second += cnt;
}
void del(map<int, int> &m, int x, int cnt = 1) {
  auto jt = m.find(x);
  if (jt->second <= cnt)
    m.erase(jt);
  else
    jt->second -= cnt;
}
const int R = 1200L;
bool cmp(const pair<pair<int, int>, int> &a,
         const pair<pair<int, int>, int> &b) {
  if (a.first.first / R != b.first.first / R)
    return a.first.first / R < b.first.first / R;
  int v = a.first.first / R;
  if (v & 1) return a.first.second > b.first.second;
  return a.first.second < b.first.second;
}
const int mod = 1000000007L;
const int maxN = 300000L;
int T, n, i, j, k, in, cnt, l, r, u, v, x, y;
int m;
vector<pair<pair<int, int>, int>> qur;
vector<int> ans, ap, arr;
vector<int> a[maxN + 5];
vector<int> f;
void chg(int x, int p) {
  if (f[x]) cnt--;
  f[x] += p;
  if (f[x]) cnt++;
}
int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  {
    cin >> n >> m;
    ap.resize(n + 1, 0);
    ans.resize(n + 1, 0);
    f.resize(n + 1, 0);
    for (i = (1); i <= (m); ++i) {
      cin >> in;
      a[in].push_back(m - i);
      ap[in] = 1;
      arr.push_back(in);
    }
    reverse(begin(arr), end(arr));
    for (i = (1); i <= (n); ++i) {
      arr.push_back(i);
      vector<int> &b = a[i];
      reverse(begin(b), end(b));
      b.push_back(m + i - 1);
      ;
      int pvr = -1;
      for (auto x : b) {
        if (pvr + 1 <= x - 1) qur.push_back({{pvr + 1, x - 1}, i});
        pvr = x;
      }
    };
    sort(begin(qur), end(qur), cmp);
    ;
    int l = 0, r = -1;
    cnt = 0;
    for (auto x : qur) {
      while (r < x.first.second) {
        r++;
        chg(arr[r], 1);
      }
      while (l > x.first.first) {
        l--;
        chg(arr[l], 1);
      }
      while (r > x.first.second) {
        chg(arr[r], -1);
        r--;
      }
      while (l < x.first.first) {
        chg(arr[l], -1);
        l++;
      };
      ans[x.second] = max(ans[x.second], cnt);
    }
    for (i = (1); i <= (n); ++i) {
      if (!ap[i]) ap[i] = i;
      cout << ap[i] << " " << ans[i] + 1 << "\n";
    }
  }
  aryanc403();
  return 0;
}
