CF1209G2.Into Blocks (hard version)

This is a harder version of the problem. In this version $q \le 200\,000$.

A sequence of integers is called nice if its elements are arranged in blocks like in $[3, 3, 3, 4, 1, 1]$. Formally, if two elements are equal, everything in between must also be equal.

Let's define difficulty of a sequence as a minimum possible number of elements to change to get a nice sequence. However, if you change at least one element of value $x$ to value $y$, you must also change all other elements of value $x$ into $y$ as well. For example, for $[3, 3, 1, 3, 2, 1, 2]$ it isn't allowed to change first $1$ to $3$ and second $1$ to $2$. You need to leave $1$'s untouched or change them to the same value.

You are given a sequence of integers $a_1, a_2, \ldots, a_n$ and $q$ updates.

Each update is of form "$i$ $x$" — change $a_i$ to $x$. Updates are not independent (the change stays for the future).

Print the difficulty of the initial sequence and of the sequence after every update.

这是一个更难的版本。在此版本中，$q \le 200\,000$。

若一个整数序列的元素以块状方式排列（例如 $[3, 3, 3, 4, 1, 1]$），则称其为“优美的”（nice）。形式化地，若序列中两个元素相等，则它们之间所有元素也必须等于该值。

我们定义一个序列的“难度”为：使其变为优美序列所需修改的最少元素个数。但有一个额外约束：若你将任意一个值为 $x$ 的元素修改为 $y$，则所有其他值为 $x$ 的元素也必须全部修改为 $y$。例如，对序列 $[3, 3, 1, 3, 2, 1, 2]$，不允许仅将第一个 $1$ 改为 $3$、而将第二个 $1$ 改为 $2$；你必须要么保持所有 $1$ 不变，要么将所有 $1$ 都改为同一个值。

给定一个整数序列 $a_1, a_2, \ldots, a_n$ 和 $q$ 次更新。

每次更新形如 “$i$ $x$” —— 将 $a_i$ 修改为 $x$。这些更新不是相互独立的（每次修改会持续影响后续状态）。

请输出初始序列的难度，以及每次更新后序列的难度。

The first line contains integers $n$ and $q$ ($1 \le n \le 200\,000$, $0 \le q \le 200\,000$), the length of the sequence and the number of the updates.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 200\,000$), the initial sequence.

Each of the following $q$ lines contains integers $i_t$ and $x_t$ ($1 \le i_t \le n$, $1 \le x_t \le 200\,000$), the position and the new value for this position.

第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 200\,000$，$0 \le q \le 200\,000$），分别表示序列的长度和更新操作的次数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 200\,000$），表示初始序列。

接下来的 $q$ 行中，每行包含两个整数 $i_t$ 和 $x_t$（$1 \le i_t \le n$，$1 \le x_t \le 200\,000$），分别表示待更新的位置及其新值。

Print $q+1$ integers, the answer for the initial sequence and the answer after every update.

输出 $q+1$ 个整数，分别为初始序列的答案以及每次更新后的答案。