假设给你一个由 $$$k$$$ 整数对 $$$(a_1, b_1), (a_2, b_2), \dots, (a_k, b_k)$$$ 组成的序列 $$$S$$$。
您可以对其执行以下操作:
1. 选择某个位置 $$$i$$$ 并将 $$$a_i$$$ 增加 $$$1$$$。仅当存在至少一个这样的位置 $$$j$$$ 使得 $$$i \ne j$$$ 且 $$$a_i = a_j$$$ 时,才可以执行该操作。该操作的成本为$$$b_i$$$;
2. 选择某个位置 $$$i$$$ 并将 $$$a_i$$$ 减少 $$$1$$$。仅当存在至少一个这样的位置 $$$j$$$ 且 $$$a_i = a_j + 1$$$ 时,才能执行此操作。此操作的成本为$$$-b_i$$$。
每个操作可以执行任意次数(可能为零)。
令 $$$f(S)$$$ 为最小可能 $$$x$$$,这样存在总成本 $$$x$$$ 的操作序列,之后来自 $$$S$$$ 的所有 $$$a_i$$$ 都是成对不同的。
现在来说说任务本身......
给定一个序列 $$$P$$$,由 $$$n$$$ 整数对 $$$(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)$$$ 组成。所有 $$$b_i$$$ 都是成对不同的。令$$$P_i$$$ 为由$$$P$$$ 的前$$$i$$$ 对组成的序列。您的任务是计算 $$$f(P_1)、f(P_2)、\dots、f(P_n)$$$ 的值。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 序列 $$$P$$$ 中的对数。
接下来的 $$$n$$$ 行包含 $$$P$$$ 的元素:接下来的 $$$n$$$ 行中的 $$$i$$$ 包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$, $$$1 \le b_i \le n$$$)。保证 $$$b_i$$$ 的所有值都是成对不同的。
输出
打印 $$$n$$$ 整数 — 第 $$$i$$$ 个数字应等于 $$$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