Задача C. Финишные позиции

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

Условие

На одном из этапов марсианских гонок по кольцевому треку вышла из строя программа, рассчитывающая финишные позиции гонщиков. На трассе имеется специальное оборудование, формирующее хронику гонки — список машин, пересекающих финишную черту. То есть, когда машина заканчивает очередной круг, пересекая финишную черту, её номер добавляется в список. Например, если список имеет вид 4 7 8 7 4 8 7 4, то это означает, что первый круг закончили машины с номерами 4 7 8 в указанном порядке, на втором круге машина 7 обогнала машину 4, а на третий круг закончили только машины 7 4, а машина 8 либо сломалась, либо всё ещё находится на втором круге.

Требуется написать программу, которая по заданному списку машин определит их финишные позиции.

По правилам марсианских кольцевых гонок гонщики, проехавшие большее количество кругов находятся на более высоких позициях, чем те, которые проехали меньшее. В группе гонщиков, проехавших одинаковое количество кругов, более высокую позицию занимает тот, кто раньше пересёк финишную черту.

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

Во входном файле содержится число N — количество элементов списка.

Далее следуют N чисел, задающие список.

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

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

Ограничения

1 ≤ N ≤ 106

Номера машин являются целыми неотрицательными числами, не превосходящими 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
5 1 10
5 1 10
2
8
4 7 8 7 4 8 7 4
7 4 8
3
16
17 88 39 88 17 39 88 17 88 17 39 39 17 39 17 222222222
17 39 88 222222222

Разбор

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

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


0.113s 0.017s 13