У вас есть $$$n$$$ дисков, радиус $$$i$$$-го диска равен $$$i$$$. Изначально эти диски распределены по $$$m$$$ башням из дисков: каждая башня содержит хотя бы один диск, и диски в каждой башне отсортированы от большего к меньшему снизу вверх.
Вы должны собрать все диски в одну башню. Чтобы сделать это, вы можете выбрать две различных башни $$$i$$$ и $$$j$$$ (каждая из которых содержит хотя бы один диск), взять несколько (возможно, все) верхних дисков с башни $$$i$$$ и поместить их на вершину башни $$$j$$$ в том же самом порядке — при условии, что верхний диск башни $$$j$$$ больше каждого перемещаемого диска. Эту операцию можно применять любое количество раз.
Например, если у вас есть две башни, содержащие диски $$$[6, 4, 2, 1]$$$ и $$$[8, 7, 5, 3]$$$ (в порядке снизу вверх), существуют ровно две возможные операции:
Пусть сложность некоторого набора башен — это минимальное количество операций, необходимых для того, чтобы собрать все диски в одну башню. Например, сложность набора башен $$$[[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
Башни в примере из условия:
Название |
---|