G. Distinctificationtime limit per test6 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard 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).InputThe 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.OutputPrint n integers — the i-th number should be equal to f(P_i).ExamplesInput51 13 35 54 22 4Output000-5-16Input42 42 32 21 1Output0371
Input51 13 35 54 22 4
Output000-5-16
['data structures', 'dsu', 'greedy', '*2900']