Допустим, у вас есть последовательность \(S\) из \(k\) пар целых чисел \((a_1, b_1), (a_2, b_2), \dots, (a_k, b_k)\).
Вы можете совершать с ней следующие операции:
- Выбрать некоторую позицию \(i\) и увеличить \(a_i\) на \(1\). Эту операцию можно делать только в том случае, если существует хотя бы одна позиция \(j\), такая, что \(i \ne j\) и \(a_i = a_j\). Стоимость такой операции равна \(b_i\);
- Выбрать некоторую позицию \(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)\).