#include <bits/stdc++.h>
using namespace std;
int n, m, now, k, a[1000005], aa[1000005], last[1000005], gm, lst[1000005], ln;
struct Node {
  int ans, l, r, num;
  void print() { printf("%d %d %d %d\n", l, r, num, ans); }
};
Node q[1000005];
int ans[300005];
void add(int x, int k) {
  for (int i = x; i <= 610005; i += i & (-i)) a[i] += k;
  return;
}
int query(int x) {
  int ans = 0;
  for (int i = x; i; i -= i & (-i)) ans += a[i];
  return ans;
}
bool cmp1(Node x, Node y) { return x.r < y.r; }
int main() {
  memset(last, -1, sizeof(last));
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n + m; i++) {
    if (i > n)
      scanf("%d", &aa[i]);
    else
      aa[i] = n + 1 - i;
    if (lst[aa[i]]) {
      q[++ln].l = lst[aa[i]];
      q[ln].r = i;
      q[ln].num = aa[i];
    }
    lst[aa[i]] = i;
  }
  for (int i = 1; i <= n; i++) {
    q[++ln].l = lst[i];
    q[ln].r = m + n + 1;
    q[ln].num = i;
  }
  sort(q + 1, q + ln + 1, cmp1);
  int j = 1;
  for (int i = 1; i <= ln; i++) {
    for (; j <= q[i].r; j++) {
      if (last[aa[j]] != -1) add(last[aa[j]], -1);
      add(j, 1);
      last[aa[j]] = j;
    }
    q[i].ans = query(q[i].r) - query(q[i].l - 1);
  }
  for (int i = 1; i <= ln; i++) {
    int tmpans = q[i].ans;
    if (q[i].r == n + m + 1) tmpans--;
    ans[q[i].num] = max(ans[q[i].num], tmpans);
  }
  for (int i = 1; i <= n; i++) printf("%d %d\n", lst[i] <= n ? i : 1, ans[i]);
}
