该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

拥挤值

题目描述

给定一条长度为 $n$ 的数轴，位置编号为 $1\sim n$。

开始时，数轴上没有任何点。

现在有 $q$ 次操作，每次操作为以下两种之一：

• 1 x：在位置 $x$ 放置一个点；
• 2 x：删除位置 $x$ 上的点。

保证所有操作均合法，即：

• 执行 1 x 时，位置 $x$ 上一定没有点；
• 执行 2 x 时，位置 $x$ 上一定有点。

对于当前数轴上的每一个点，定义它的拥挤值为：

• 若当前数轴上只有这一个点，则它的拥挤值为 $0$；
• 否则，它的拥挤值等于它到最近的另一个点的距离。

你需要在每次操作后，输出当前所有点的拥挤值之和。

任意时刻，每个位置至多存在一个点。

输入格式

第一行输入两个整数 $n,q$，分别表示数轴长度和操作次数。

接下来 $q$ 行，每行输入两个整数 op 和 $x$，表示一次操作。

保证所有操作合法。

数据范围

• $1 \le n \le 10^9$
• $1 \le q \le 2\times 10^5$
• $op \in {1,2}$
• $1 \le x \le n$

输出格式

对于每次操作，输出一行一个整数，表示当前所有点的拥挤值之和。

输入输出样例 #1

输入 #1

10 7
1 4
1 9
1 6
1 2
2 6
1 8
2 4

输出 #1

0
10
7
9
9
6
8

说明/提示

记当前数轴上的点集为 $S$。

• 第 1 次操作 1 4：当前 $S={4}$。位置 $4$ 没有其他点，拥挤值为 $0$。当前总拥挤值为：$0$。
• 第 2 次操作 1 9：当前 $S={4,9}$。位置 $4$ 最近点为 $9$，拥挤值为 $5$；位置 $9$ 最近点为 $4$，拥挤值为 $5$。当前总拥挤值为：$5+5=10$。
• 第 3 次操作 1 6：当前 $S={4,6,9}$。位置 $4$ 最近点为 $6$，拥挤值为 $2$；位置 $6$ 最近点为 $4$ 或 $9$，拥挤值为 $2$；位置 $9$ 最近点为 $6$，拥挤值为 $3$。当前总拥挤值为：$2+2+3=7$。
• 第 4 次操作 1 2：当前 $S={2,4,6,9}$。位置 $2,4,6$ 的拥挤值均为 $2$，位置 $9$ 最近点为 $6$，拥挤值为 $3$。当前总拥挤值为：$2+2+2+3=9$。
• 第 5 次操作 2 6：当前 $S={2,4,9}$。位置 $2,4$ 的拥挤值均为 $2$，位置 $9$ 最近点为 $4$，拥挤值为 $5$。当前总拥挤值为：$2+2+5=9$。
• 第 6 次操作 1 8：当前 $S={2,4,8,9}$。位置 $2,4$ 拥挤值均为 $2$，位置 $8,9$ 拥挤值均为 $1$。当前总拥挤值为：$2+2+1+1=6$。
• 第 7 次操作 2 4：当前 $S={2,8,9}$。位置 $2$ 最近点为 $8$，拥挤值为 $6$，位置 $8,9$ 拥挤值均为 $1$。当前总拥挤值为：$6+1+1=8$。

备注

• 对于任意两个位置 $a,b$，它们之间的距离定义为 $|a-b|$。