Suppose 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:
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)$$$.
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.
Print $$$n$$$ integers — the $$$i$$$-th number should be equal to $$$f(P_i)$$$.
5
1 1
3 3
5 5
4 2
2 4
0
0
0
-5
-16
4
2 4
2 3
2 2
1 1
0
3
7
1
Name |
---|