Distinctification

题目描述

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: 1. 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 $ ; 2. 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) $ .

输入输出格式

输入格式

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) $ .

输入输出样例

输入样例 #1

5
1 1
3 3
5 5
4 2
2 4

输出样例 #1

0
0
0
-5
-16

输入样例 #2

4
2 4
2 3
2 2
1 1

输出样例 #2

0
3
7
1