Пасьянс по-иркутски

Дед Василий с дальней заимки, коротая долгие зимние вечера, придумал следующий пасьянс: пусть в ряд разложено n карт, на каждой из которых написано по одному числу: a₁,a₂,…,a_n. Дед Василий просматривает эти карты слева направо и некоторые из них перекладывает в правый конец ряда. Условием перемещения карты является наличие справа от неё хотя бы одной карты с большим чем у неё значением. Более строго: карта на позиции i и значением a_i будет перемещена вправо, если найдётся позиция j > i такая, что a_j > a_i. Пасьянс считается законченным, когда дед Василий доходит до самой правой на данный момент карты.

Иногда пасьянс затягивается уж очень надолго. Поэтому дед Василий задался вопросом: как по исходному расположению карт выяснить, сколько перекладываний придётся сделать.

Входные данные

В первой строке входного файла INPUT.TXT находится одно целое число n (1 ≤ n ≤ 10⁶) — количество карт в пасьянсе.

Во второй строке содержится n целых чисел a_i через пробел — описание исходного расположения карт на столе слева направо (1 ≤ a_i ≤ 10⁹).

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число — количество карт, которые придётся переложить прежде, чем пасьянс сойдётся.

Пример

Пояснение к примеру

Рассмотрим пример 3 7 6 8 5 8 2 1 7 6. При просмотре слева направо, можно увидеть, что карты 3 7 6 5 2 1 (в позициях 1 2 3 5 7 8) имеют справа от себя карту с большим значением и поэтому будут перемещены в таком порядке вправо. После перемещения этих карт получится 8 8 7 6 3 7 6 5 2 1 и мы дошли до теперь первой слева карты 6.

Продолжим перемещение и получим, что будут перемещены карты 6 и 3 (позиции 4 5 в новом наборе), так как справа от них есть карта со значением 7, получим 8 8 7 7 6 5 2 1 6 3.

Далее будут перемещены карты 5 2 1 (позиции 6 7 8), получим 8 8 7 7 6 6 3 5 2 1.

Теперь извлекается 3 с позиции 7 и получится 8 8 7 7 6 6 5 2 1 3.

Наконец перемещаются 2 1 (позиции 8 9) и получается 8 8 7 7 6 6 5 3 2 1.

Если подсчитать количество произведённых перемещений, то получим 14.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]