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

假设你得到一个由 $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$ 两两互不相同。

现在进入本题任务本身……

你被给定一个由 $n$ 个整数对 $(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)$ 构成的序列 $P$，其中所有 $b_i$ 两两互不相同。令 $P_i$ 表示由 $P$ 的前 $i$ 个整数对构成的序列。你的任务是计算 $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.

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——表示序列 $P$ 中的数对个数。

接下来 $n$ 行包含序列 $P$ 的元素：其中第 $i$ 行（即接下来的 $n$ 行中的第 $i$ 行）包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i \le 2 \cdot 10^5$，$1 \le b_i \le n$）。保证所有 $b_i$ 的值两两不同。

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

输出 $n$ 个整数——第 $i$ 个数应等于 $f(P_i)$。