Допустим, у вас есть последовательность $$$S$$$ из $$$k$$$ пар целых чисел $$$(a_1, b_1), (a_2, b_2), \dots, (a_k, b_k)$$$.

Вы можете совершать с ней следующие операции:

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$$$, после которой все $$$a_i$$$ в $$$S$$$ станут попарно различными.

А теперь, собственно, сама задача.

Вам дана последовательность $$$P$$$, состоящая из $$$n$$$ пар целых чисел $$$(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)$$$. Все значения $$$b_i$$$ попарно различны. Пусть $$$P_i$$$ — это последовательность, состоящая из первых $$$i$$$ пар из $$$P$$$. Ваша задача — подсчитать $$$f(P_1), f(P_2), \dots, f(P_n)$$$.