Description

小黄的东西太乱了，小杨很不爽，想要帮小黄把东西弄整齐。

小黄的物品被摆放为一个长度为 $n$ 的序列，小杨认为这个序列是整齐的，当且仅当序列满足以下状态：只要序列中存在元素 $x$，那么所有的元素 $x$ 都必须在序列中连续（一种元素 $x$ 在序列中连续当且仅当序列中只有 $1$ 个元素 $x$，或任意两个元素 $x$ 之间没有或只存在元素 $x$）。小杨每次可以将 $\texttt{所有}$ 的元素 $x$ 改成任意的元素 $y$，同时花费修改元素数量的代价。小杨想要知道将这个序列变得整齐所需要花费的最小代价。

但是小黄做事马马虎虎的，将会有 $q$ 次改变序列。每次改变序列，都会永久的把序列的第 $t$ 个元素修改为 $c$，因此每次小黄修改序列后，小杨都会想重新知道把新序列变整齐的代价。请你告诉小杨将初始序列变得整齐所需要的最小代价和每次改变序列后所需的最小代价。

Format

Input

第一行包含两个整数 $n, q\ (1 \leq n, q \leq 2 \times 10^5)$，表示序列的大小和小黄修改序列的次数。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n\ (1 \leq a_i \leq 2 \times 10^5)$，表示序列中的元素。

接下来 $q$ 行，每行两个整数 $t_i, c_i\ (1 \leq t_i \leq n, 1 \leq c_i \leq 2 \times 10^5)$，表示第 $q$ 次修改序列时小黄将 $a_t$ 修改成了 $c$。

Output

输出 $q + 1$ 行，每行一个整数，表示原始序列和每次改变后的序列弄整齐需要的最小代价。

Samples

5 2
1 2 1 2 1
2 1
5 3

2
1
0

Note

对于样例一，对原始序列，只要选择将元素 $2$ 变成元素 $1$，就可以满足序列中只存在元素 $1$ 并且连续，代价为 $2$。

第一次改变序列后，序列变成 $[1, 1, 1, 2, 1]$，其中元素 $1$ 不连续，只要选择将元素 $2$ 变成元素 $1$，就可以满足序列中只存在元素 $1$ 并且连续，代价为 $1$。

第二次改变序列后，序列变成 $[1, 1, 1, 2, 3]$，其中存在元素 $1, 2, 3$，在序列中都连续出现，因此不需要代价。

Limitation

1s, 1024KiB for each test case.