[R64D]路灯 - 代码源竞赛平台

时空限制

1.5S/512M

题目描述

在一长条街区中，共有 $10^9$ 个路灯位置，从左到右依次编号为 $1, 2, \dots, 10^9$。最开始，所有的路灯均处于熄灭状态。

为了保障行车与步行安全，市政部门需要实时评估当前街区的黑暗程度。

现在会有 $Q$ 次操作，每次操作会给定一个路灯编号 $x$，你需要切换编号为 $x$ 的路灯的状态（即：如果该路灯当前是熄灭的，则将其点亮；如果当前是点亮的，则将其熄灭）。

若当前所有已点亮的路灯位置从小到大排列为：$p_1 < p_2 < \dots < p_k$，对于每一对相邻的已点亮路灯 $(p_i, p_{i+1})$，设它们之间处于熄灭状态的路灯数量为 $d$，即 $d = p_{i+1} - p_i - 1$，这一段的黑暗程度为 $d^2$。

整条街区的黑暗程度为所有相邻已点亮路灯之间的黑暗程度的和，即：$\sum_{i=1}^{k-1} (p_{i+1} - p_i - 1)^2$。

如果当前点亮的路灯少于 $2$ 盏，则黑暗程度定义为 $0$。

在每次切换操作完成后，你都需要计算并输出当前所有已点亮路灯之间的整条街区的黑暗程度。

格式

输入格式

第一行包含一个正整数 $Q$，表示操作的数量。

接下来 $Q$ 行，每行包含一个正整数 $x$，表示当前需要切换状态的路灯编号。

输出格式

输出共 $Q$ 行，第 $i$ 行输出一个整数，表示当前所有已点亮路灯之间的黑暗程度。

样例

样例输入 #1

5
3
8
5
5
10

样例输出 #1

0
16
5
16
17

样例输入 #2

2
400000000
1000000000

样例输出 #2

0
359999998800000001

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$Q\le$
$1$	$40$	$5000$
$2$	$60$	$2\times 10^5$

对于 $100\%$ 的数据，$1 \le Q \le 2 \times 10^5$，$1 \le x \le 10^9$。