Points solution codeforces – A triple of points 𝑖i, 𝑗j and 𝑘k on a coordinate line is called beautiful if 𝑖<𝑗<𝑘i<j<k and 𝑘−𝑖≤𝑑k−i≤d.
[Solution] Points solution codeforces
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≤𝑞,𝑑≤2⋅1051≤q,d≤2⋅105) — the number of queries and the parameter for defining if a triple is beautiful, respectively.
The second line contains 𝑞q integers 𝑎1,𝑎2,…,𝑎𝑞a1,a2,…,aq (1≤𝑎𝑖≤2⋅1051≤ai≤2⋅105) denoting the queries. The integer 𝑎𝑖ai denotes the 𝑖i-th query in the following way:
- if the point 𝑎𝑖ai belongs to the set, remove it; otherwise, add it;
- after adding or removing the point, print the number of beautiful triples.
[Solution] Points solution codeforces
For each query, print one integer — the number of beautiful triples after processing the respective query.
Example
input
Copy
7 5 8 5 3 2 1 5 6
output
Copy
0 0 1 2 5 1 5