Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-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.

No tag edit access

G. Distinctification

time limit per test

6 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputSuppose you are given a sequence $$$S$$$ of $$$k$$$ pairs of integers $$$(a_1, b_1), (a_2, b_2), \dots, (a_k, b_k)$$$.

You can perform the following operations on it:

- Choose some position $$$i$$$ and increase $$$a_i$$$ by $$$1$$$. That can be performed only if there exists at least one such position $$$j$$$ that $$$i \ne j$$$ and $$$a_i = a_j$$$. The cost of this operation is $$$b_i$$$;
- Choose some position $$$i$$$ and decrease $$$a_i$$$ by $$$1$$$. That can be performed only if there exists at least one such position $$$j$$$ that $$$a_i = a_j + 1$$$. The cost of this operation is $$$-b_i$$$.

Each operation can be performed arbitrary number of times (possibly zero).

Let $$$f(S)$$$ be minimum possible $$$x$$$ such that there exists a sequence of operations with total cost $$$x$$$, after which all $$$a_i$$$ from $$$S$$$ are pairwise distinct.

Now for the task itself ...

You are given a sequence $$$P$$$ consisting of $$$n$$$ pairs of integers $$$(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)$$$. All $$$b_i$$$ are pairwise distinct. Let $$$P_i$$$ be the sequence consisting of the first $$$i$$$ pairs of $$$P$$$. Your task is to calculate the values of $$$f(P_1), f(P_2), \dots, f(P_n)$$$.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of pairs in sequence $$$P$$$.

Next $$$n$$$ lines contain the elements of $$$P$$$: $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$, $$$1 \le b_i \le n$$$). It is guaranteed that all values of $$$b_i$$$ are pairwise distinct.

Output

Print $$$n$$$ integers — the $$$i$$$-th number should be equal to $$$f(P_i)$$$.

Examples

Input

5

1 1

3 3

5 5

4 2

2 4

Output

0

0

0

-5

-16

Input

4

2 4

2 3

2 2

1 1

Output

0

3

7

1

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2018 02:16:38 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|