Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

(Время: 5 сек. Память: 256 Мб Сложность: 76%)

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

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

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

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

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

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

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

Пример

INPUT.TXTOUTPUT.TXT
110
3 7 6 8 5 8 2 1 7 6
14

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

Рассмотрим пример 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.


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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 A. Дистанционное обучение
 B. Код от сейфа
 C. Всеобъемлющая Галактическая Магистральная Сеть
 D. ДНК-палиндром
 E. Разлад Империй
 F. Раздача Фибоначчи
 G. Карты, числа, два заклинания
 H. Гипноз
 I. Круговой марафон
 J. Пасьянс по-иркутски
 K. Shark Attack

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru