Это сложная версия задачи. В данной версии $$$q \le 200\,000$$$.

Последовательность чисел называется хорошей, если элементы разбиты на блоки как в $$$[3, 3, 3, 4, 1, 1]$$$. Формально, если два элемента равны, то все элементы между ними должны быть тоже равны тому же значению.

Определим сложность последовательности как минимальное число элементов, которое нужно поменять, чтобы получить хорошую последовательность. Однако, если вы заменяете хотя бы один $$$x$$$ на какое-то значение $$$y$$$, нужно заменить все остальные значения $$$x$$$ на $$$y$$$ тоже. Например, для $$$[3, 3, 1, 3, 2, 1, 2]$$$ не разрешается поменять первую $$$1$$$ на $$$3$$$, а вторую $$$1$$$ на $$$2$$$. Вы можете или не заменять $$$1$$$ совсем, или заменить их все на что-то одно.

Вам дана последовательность целых чисел $$$a_1, a_2, \ldots, a_n$$$ и $$$q$$$ изменений.

Каждое изменение имеет вид «$$$i$$$ $$$x$$$» — заменить $$$a_i$$$ на $$$x$$$.

Выведите сложность изначальной последовательности и последовательности после каждого изменения. Обратите внимание, что изменения не независимы (изменение сохраняется на будущее).