Поликарп — частый пользователь одного очень популярного мессенджера. Он постоянно общается со своими друзьями. У него есть \(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]\).
Для каждого друга рассмотрим, на каких позициях он был в самом начале и после получения каждого сообщения. Поликарп хочет знать, какие были минимальная и максимальная позиции.
Примечание
В первом примере список последних диалогов Поликарпа выглядит так:
- \([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]\)