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

У вас есть $$$n$$$ дисков, радиус $$$i$$$-го диска равен $$$i$$$. Изначально эти диски распределены по $$$m$$$ башням из дисков: каждая башня содержит хотя бы один диск, и диски в каждой башне отсортированы от большего к меньшему снизу вверх.

Вы должны собрать все диски в одну башню. Чтобы сделать это, вы можете выбрать две различных башни $$$i$$$ и $$$j$$$ (каждая из которых содержит хотя бы один диск), взять несколько (возможно, все) верхних дисков с башни $$$i$$$ и поместить их на вершину башни $$$j$$$ в том же самом порядке — при условии, что верхний диск башни $$$j$$$ больше каждого перемещаемого диска. Эту операцию можно применять любое количество раз.

Например, если у вас есть две башни, содержащие диски $$$[6, 4, 2, 1]$$$ и $$$[8, 7, 5, 3]$$$ (в порядке снизу вверх), существуют ровно две возможные операции:

  • переместить диск $$$1$$$ с первой башни на вторую, после чего башни станут следующими: $$$[6, 4, 2]$$$ и $$$[8, 7, 5, 3, 1]$$$;
  • переместить диски $$$[2, 1]$$$ с первой башни на вторую, после чего башни станут следующими: $$$[6, 4]$$$ и $$$[8, 7, 5, 3, 2, 1]$$$.

Пусть сложность некоторого набора башен — это минимальное количество операций, необходимых для того, чтобы собрать все диски в одну башню. Например, сложность набора башен $$$[[3, 1], [2]]$$$ равна $$$2$$$: вы можете переместить диск $$$1$$$ на вторую башню, а потом переместить оба диска со второй башни на первую башню.

Вам заданы $$$m - 1$$$ запросов. Каждый запрос обозначается двумя числами $$$a_i$$$ и $$$b_i$$$, обозначающими следующее: «слить башни $$$a_i$$$ и $$$b_i$$$ в одну» (то есть взять все диски из этих башен и составить из них одну башню, в которой диски отсортированы по убыванию размера снизу вверх). Новая башня (являющаяся результатом слияния) получает индекс $$$a_i$$$.

Для каждого $$$k \in [0, m - 1]$$$ посчитайте сложность набора башен после выполнения первых $$$k$$$ запросов.

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le m \le n \le 2 \cdot 10^5$$$) — количество дисков и башен, соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$t_1$$$, $$$t_2$$$, ..., $$$t_n$$$ ($$$1 \le t_i \le m$$$), где $$$t_i$$$ — индекс башни, к которой принадлежит диск $$$i$$$. Каждое значение от $$$1$$$ до $$$m$$$ встречается в этой последовательности хотя бы один раз.

Затем следуют $$$m - 1$$$ строк, обозначающих запросы. Каждый запрос задается двумя целыми числами $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le m$$$, $$$a_i \ne b_i$$$), обозначающими, что во время $$$i$$$-го запроса башни $$$a_i$$$ и $$$b_i$$$ сливаются в одну ($$$a_i$$$ и $$$b_i$$$ всегда выбраны таким образом, что башни с этими номерами существуют до $$$i$$$-го запроса).

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

Выведите $$$m$$$ целых чисел. $$$k$$$-е число (в $$$0$$$-индексации) должно быть равно сложности набора башен после первых $$$k$$$ запросов.

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

Башни в примере из условия:

  • до запросов: $$$[[5, 1], [2], [7, 4, 3], [6]]$$$;
  • после первого запроса: $$$[[2], [7, 5, 4, 3, 1], [6]]$$$;
  • после второго запроса: $$$[[7, 5, 4, 3, 2, 1], [6]]$$$;
  • после третьего запроса остается только одна башня: $$$[7, 6, 5, 4, 3, 2, 1]$$$.