E. Симулятор мессенджера
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп — частый пользователь одного очень популярного мессенджера. Он постоянно общается со своими друзьями. У него есть $$$n$$$ друзей, пронумерованных от $$$1$$$ до $$$n$$$.

Напомним, что перестановка размера $$$n$$$ — это такой массив размера $$$n$$$, что каждое число от $$$1$$$ до $$$n$$$ встречается в нем ровно один раз.

Так что его список последних диалогов может быть представлен в виде перестановки $$$p$$$ размера $$$n$$$. $$$p_1$$$ — это самые недавний диалог, $$$p_2$$$ — второй по давности и так далее.

Изначально список диалогов Поликарпа $$$p$$$ выглядит как $$$1, 2, \dots, n$$$ (другими словами, является тождественной перестановкой).

После этого он получает $$$m$$$ сообщений, $$$j$$$-е сообщение приходит от друга $$$a_j$$$. Тогда друг $$$a_j$$$ перемещается на первую позицию в перестановке, сдвигая всех между первой позицией и текущей позицией $$$a_j$$$ на $$$1$$$. Обратите внимание, что если друг $$$a_j$$$ уже стоит на первой позиции, то ничего не происходит.

Например, пусть список последних диалогов будет $$$p = [4, 1, 5, 3, 2]$$$:

  • если он получает сообщение от друга $$$3$$$, то $$$p$$$ становится $$$[3, 4, 1, 5, 2]$$$;
  • если он получает сообщение от друга $$$4$$$, то $$$p$$$ не меняется $$$[4, 1, 5, 3, 2]$$$;
  • если он получает сообщение от друга $$$2$$$, то $$$p$$$ становится $$$[2, 4, 1, 5, 3]$$$.

Для каждого друга рассмотрим, на каких позициях он был в самом начале и после получения каждого сообщения. Поликарп хочет знать, какие были минимальная и максимальная позиции.

Входные данные

В первой строке записаны два целых числа $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$) — количество друзей Поликарпа и количество полученных сообщений, соответственно.

Во второй строке записаны $$$m$$$ целых чисел $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_i \le n$$$) — описания полученных сообщений.

Выходные данные

Выведите $$$n$$$ пар целых чисел. Для каждого друга выведите минимальную и максимальную позиции, на которых он был в самом начале и после получения каждого сообщения.

Примеры
Входные данные
5 4
3 5 1 4
Выходные данные
1 3
2 5
1 4
1 5
1 5
Входные данные
4 3
1 2 4
Выходные данные
1 3
1 2
3 4
1 4
Примечание

В первом примере список последних диалогов Поликарпа выглядит так:

  • $$$[1, 2, 3, 4, 5]$$$
  • $$$[3, 1, 2, 4, 5]$$$
  • $$$[5, 3, 1, 2, 4]$$$
  • $$$[1, 5, 3, 2, 4]$$$
  • $$$[4, 1, 5, 3, 2]$$$

Так что, например, позиции друга $$$2$$$ — $$$2, 3, 4, 4, 5$$$, соответственно. Из всех них $$$2$$$ — это минимум, а $$$5$$$ — это максимум. Поэтому ответ для друга $$$2$$$ — это пара $$$(2, 5)$$$.

Во втором примере список последних диалогов Поликарпа выглядит так:

  • $$$[1, 2, 3, 4]$$$
  • $$$[1, 2, 3, 4]$$$
  • $$$[2, 1, 3, 4]$$$
  • $$$[4, 2, 1, 3]$$$