F. Points
time limit per test
6.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A triple of points $i$, $j$ and $k$ on a coordinate line is called beautiful if $i < j < k$ and $k - i \le d$.

You are given a set of points on a coordinate line, initially empty. You have to process queries of three types:

• add a point;
• remove a point;
• calculate the number of beautiful triples consisting of points belonging to the set.
Input

The first line contains two integers $q$ and $d$ ($1 \le q, d \le 2 \cdot 10^5$) — the number of queries and the parameter for defining if a triple is beautiful, respectively.

The second line contains $q$ integers $a_1, a_2, \dots, a_q$ ($1 \le a_i \le 2 \cdot 10^5$) denoting the queries. The integer $a_i$ denotes the $i$-th query in the following way:

• if the point $a_i$ belongs to the set, remove it; otherwise, add it;
• after adding or removing the point, print the number of beautiful triples.
Output

For each query, print one integer — the number of beautiful triples after processing the respective query.

Example
Input
7 5
8 5 3 2 1 5 6

Output
0
0
1
2
5
1
5