Задача B. Построение солдат - 2

Входной файл:input.txt   Ограничение времени:5 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

В армии некоторого государства построение солдат по росту производится следующим образом: сначала выбирается самый высокий солдат, после чего он несколькими последовательными переменами местами с непосредственными соседями передвигается в начало строя. Далее выбирается самый высокий из оставшихся и ставится на второе место и т. д. Если в строю несколько солдат имеют наибольший рост, то из них выбирается тот, который стоит ближе к началу строя.
Один талантливый полководец заметил, что построение таким образом занимает слишком много времени и придумал свой способ. Для того, чтобы убедить свое консервативное начальство в необходимости применения его метода, полководец решил подсчитать, сколько перемен местами соседних солдат требовалось при использовании старого способа. Таким образом он хотел доказать, что подобная процедура слишком утомительна для солдат. Помогите ему решить эту задачу.

Формат входного файла

Первая строка содержит число солдат N. В последующих строках содержатся N описаний каждого солдата: рост Ri и имя Si.

Формат выходного файла

В выходном файле должно содержаться единственное число - количество перемен местами, необходимых для построения солдат в шеренгу от самого высокого к самому низкому.

Ограничения

1 ≤ N ≤ 100000 0 ≤ Ri ≤ 1000000 (действительное число)
Длина имени солдата не превосходит 255 символов.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1

3
1.75 name1
1.70 name2
1.76 name3
    

2
    

0.097s 0.019s 15