Задача №3701. Посадка в поезд
Цифровой поезд нового поколения состоит из вагонов, содержащих по \(N\) мест для пассажиров. Все места расположены вдоль вагона и пронумерованы от \(1\) до \(N\). Вход в вагон расположен левее места \(1\), а места \(1, 2, \ldots, N\) расположены правее от входа в соответствующем порядке. \(N\) пассажиров готовятся сесть в поезд. Каждый заходящий в вагон характеризуется номером места \(A_i\) и своей массой \(B_i\). Когда пассажир идет по вагону от входа до своего места, некоторые пассажиры, которые сели ранее, мешают ему пройти. Пассажир испытывает неудобство, каждый раз проходя мимо человека массы большей, чем у него самого. Суммарным неудобством пассажира при посадке называется количество раз, когда он испытывал неудобство при движении к своему месту от входа в вагон. Ваша задача — по заданному порядку посадки пассажиров найти суммарное неудобство каждого.
Входной файл состоит из одного или нескольких наборов входных данных. Каждый набор начинается с целого числа \(N\; (1 \leq N \leq 100\,000)\) — количества мест (пассажиров). Далее набор входных данных содержит пары целых чисел \(A_i, B_i\; (1 \leq A_i \leq N, 1 \leq B_i \leq 10^9)\). Все числа \(A_i\) и \(B_i\) различны между собой. То есть номера мест пассажиров образуют перестановку. Пассажиры садятся в поезд именно в том порядке, в котором они заданы во входном файле. Количество наборов входных данных не превосходит \(5\).
Выведите ответ на каждый набор входных данных. Каждый ответ должен состоять из последовательности \(N\) целых чисел \(P_1, P_2, \ldots, P_N\), где \(P_i\) — суммарное неудобство \(i\)-го пассажира.
3 1 2 2 3 3 1 2 1 1 2 2
0 0 2 0 0