Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

data structures

implementation

math

matrices

*2500

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Points

time limit per test

6.5 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputA 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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/15/2024 12:40:05 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|