一条笔直的道路上有 $N$ 盏路灯。第 $i$ 盏路灯的初始高度为一个正整数 $A_i$ ($1 \le i \le N$)。

你试图在两盏路灯之间安装电线。若要在路灯 $i$ 和路灯 $j$ ($j > i$) 之间安装电线，必须满足以下条件：

• $A_i = A_j$
• 对于所有 $i < k < j$，满足 $A_k < A_i$。

城市管理部门可能会对路灯高度进行 $Q$ 次调整。每次调整由一对正整数 $(x, h)$ 给出，表示第 $x$ 盏路灯的高度被调整为 $h$。换句话说，$A_x = h$。

在初始状态以及每次更新后，请计算满足可以在路灯 $i$ 和 $j$ ($1 \le i < j \le N$) 之间安装电线的对数。

输入格式

第一行包含两个整数 $N$ 和 $Q$ ($2 \le N \le 100\,000$, $1 \le Q \le 250\,000$)。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$)。

接下来的 $Q$ 行，每行包含两个整数 $x$ 和 $h$，表示在查询后 $A_x = h$ ($1 \le x \le N$, $1 \le h \le 10^9$)。保证 $h$ 与更新前第 $x$ 盏路灯的高度不同。

输出格式

输出 $Q + 1$ 行。第 $i$ 行 ($1 \le i \le Q + 1$) 输出处理完前 $i - 1$ 次更新查询后，可以安装电线的路灯对数。

样例

输入 1

6 2
4 2 2 2 4 6
4 6
6 4

输出 1

3
2
2