Задача A. Сумма двух чисел ≡

Условие

Вывести сумму двух заданных чисел.

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

На первой строке входного файла находятся два целых числа a и b ( − 10⁹ ≤ a, b ≤ 10⁹).

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

Вашей программе требуется вывести единственное число — сумму заданных чисел a + b.

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

2 3

5

17 -18

-1

Задача AA. Сколько селёдок? ≡

Условие

Витя, Петя и Олег решили сходить на рыбалку за селёдками. В море селёдок много и каждая из них весит строго целое количество килограмм. Олег провёл классификацию рыбы и выяснил, что массы селёдок образуют последовательность, заданную следующим образом: x_i = x_i − 1 + i. Минимальный вес селёдки составляет один килограмм. Мальчики взяли с собой ведро, в которое помещается N килограмм рыбы. Разумеется, они хотели бы вернуться домой с полным ведром селёдок.

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

Формат входных данных

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

Формат выходных данных

В выходной файл выведите число — минимальное число селёдок.

Ограничения

1 ≤ N ≤ 5 * 10¹¹

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

3

1

5

3

Задача B. Точка в углу ≡

Условие

Прямоугольник со сторонами, параллельными осям координат, задан координатами противоположных вершин (x₁, y₁) и (x₂, y₂).

Будем считать, что точка (x, y) внутри прямоугольника находится в углу, если расстояние от точки до одной из вершин прямоугольника строго меньше, чем до центра прямоугольника.

Напишите программу, которая по данному прямоугольнику и точке определяет, находится ли точка в углу.

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

Входной файл содержит целые числа x₁ y₁ x₂ y₂ x y — координаты вершин прямоугольника и точки.

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

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

Ограничения

 − 10⁴ ≤ x₁,y₁,x₂,y₂ ≤ 10⁴

min(x₁, x₂) ≤ x ≤ max(x₁, x₂)

min(y₁, y₂) ≤ y ≤ max(y₁, y₂)

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

100 200 300 400 290 210

CORNER

100 200 300 400 200 300

CENTER

Задача C. Сумма элементов последовательности ≡

Условие

Последовательность b_i получается из последовательности a_i по следующему закону: b_i = ( − 1)^a_i.

Требуется написать программу, вычисляющую сумму N элементов последовательности b_i.

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

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

Далее следует N чисел, задающих последовательность a_i.

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

В выходном файле должно содержаться единственное число — сумма всех элементов последовательности b_i.

Ограничения

1 ≤ N ≤ 10⁶

0 ≤ |a_i| ≤ 10⁹

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

4
1 7 12 13

-2

6
-1 -2 -3 -4 -5 -6

0

Задача D. Массив наоборот ≡

Условие

Во входном файле дан массив целых чисел a₁, a₂, ..., a_N. Требуется вывести этот массив в обратном порядке.

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

Входной файл содержит целое число N, за которым следуют N целых чисел a_i.

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

Выходной файл должен содержать N чисел — массив a_i, записанный в обратном порядке.

Ограничения

1 ≤ N ≤ 100000

 − 10⁹ ≤ a_i ≤ 10⁹

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

4
1 2 3 4

4 3 2 1

6
9 1 3 -2 3 5

5 3 -2 3 1 9

Задача E. Вид из окна ≡

Условие

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

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

Формат входных данных

Входные данные содержат целые число n — количество мест в электричке. Далее следует n целых чисел a_i — уровень загрязнения i-го окна. Окна нумеруются с единицы.

Формат выходных данных

Ответ — одно целое число.

Ограничения

5 ≤ n ≤ 10000

1 ≤ a_i ≤ 10000

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

6
10 2 3 3 2 1

4

Задача F. Максимальный перепад ≡

Условие

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

Карта региона представляет собой матрицу размером N x N клеток, в каждой клетке которой содержится средняя высота определённого района над уровнем моря. Максимальным перепадом высот называется максимальная величина, на которую отличаются средние высоты двух районов, соседних на карте по горизонтали или по вертикали. Требуется по карте региона определить максимальный перепад высот в нем.

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

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

Ограничения

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

3
1 1 1
1 2 1
1 2 3

2

Задача G. План эвакуации ≡

Условие

В городе, где живет юный программист Вася, построили школу. Когда в школу пошли первые ученики, выяснилось, что план эвакуации в основном коридоре составлен неправильно.

Коридор является одномерным и состоит из N клеток, в каждой клетке может находиться только один человек

План эвакуации представляет из себя строку из N символов 'L', 'R', 'X'. Символ 'L' означает, что человек, находящийся в данной клетке, в случае эвакуации должен пойти в соседнюю клетку слева. Аналогично, символ 'R' означает, что следует пойти вправо. Символ 'X' означает, что в этой клетке расположен выход.

Предполагается, что при эвакуации в каждой клетке, кроме выходов, будет располагаться один человек и все они начнут двигаться согласно плану эвакуации. Каждый будет выходить в первый выход, который встретится у него на пути.

Чтобы план эвакуации был безопасным, в каждый выход не должно попасть более, чем K человек. Также, при эвакуации люди не должны столкнуться друг с другом.

Вам требуется написать программу, которая предложит безопасный план эвакуации.

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

Первая строка входного файла содержит числа N, M и K — размер описания плана эвакуации, количество выходов и ограничение на каждый выход.

Вторая строка входного файла содержит M целых чисел x_i — координаты выходов. Координаты заданы в порядке возрастания.

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

В выходной файл выведите единственную строку — описание плана эвакуации, удовлетворяющего всем вышеописанным условиям, или строку NO, если такого плана не существует.

Ограничения

1 ≤ M ≤ N ≤ 10⁵

1 ≤ K ≤ 10⁵

1 ≤ x_i ≤ N

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

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

6 1 7
5

RRRRXL

10 1 5
5

NO

Задача H. Максимальный элемент массива ≡

Условие

Вам необходимо написать программу, которая находит наибольший элемент в массиве.

Формат входных данных

В первой строке записано одно целое число N — количество элементов в массиве.

Далее следует N целых чисел a_i — элементы массива.

Формат выходных данных

Выведите единственное целое число — наибольший элемент массива.

Ограничения

1 ≤ N ≤ 10³

 − 10⁶ ≤ a_i ≤ 10⁶

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Подсказка

Для того чтобы считывать элементы массива на языке Pascal следует использовать функцию read(). Применение функции readln() невозможно, так как все элементы массива записаны в одной строке.

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

3
1 3 2

3

5
8 5 6 10 3

10

1
1000000

1000000

Задача I. Факториал ≡

Условие

Для заданного натурального числа N выведите значение N!

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

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

Ограничения

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

3

6

Задача J. Фибоначчи_rec ≡

Условие

Необходимо вывести N первых чисел Фибоначчи, начиная с 0.

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

Входной файл содержит одно целое неотрицательное число N.

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

Выходной файл должен содержать N первых чисел последовательности Фибоначчи.

Ограничения

Unbalanced TeX0 ≤ N ≤ 10

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

2

0 1

Задача J. Код Хаффмана ≡

Условие

Построить код Хаффмана для алфавита из N символов и соответствующих им частот встречаемости.

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

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

Ограничения

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

6
45
13
12
16
9
5

0
101
100
111
1101
1100

Задача K. Два компьютера ≡

Условие

Имеется два компьютера с одинаковой производительностью и N программ, которые необходимо выполнить. Известно, что i-я программа требует для выполнения на любом из компьютеров T_i секунд. Программы можно выполнять в любом порядке, но прерывать однажды запущенную программу нельзя. Сразу после окончания одной программы можно запускать следующую.

Требуется распределить программы между компьютерами таким образом, чтобы время на их выполнение оказалось наименьшим. Например, программы длительностью 7, 10, 3, 5, 6 можно выполнить за 16 секунд, если на первом компьютере выполнять вторую и четвертую программу, а на втором — остальные три.

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

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

Ограничения

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

5 7 10 3 5 6

16

Задача L. Короткий текст и немного слов ≡

Условие

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

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

Ограничения

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

Longlongstring
2
short
string

0 1

Задача M. Укорачивание текста ≡

Условие

По заданному тексту длины N и образцу длины K определить длину минимальной подстроки в тексте, которая удовлетворяет данному образцу. Текст состоит только из маленьких латинских букв. Образец содержит маленькие латинские буквы и символ '*', заменяющий любое множество любых символов(в том числе пустое).

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

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

В выходном файле должно находится единственное число — минимальная длина искомой подстроки, или  − 1, если образец в тексте не встречается.

Ограничения

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

3 4
a*b
abab

2

Задача N. Дифтонги ≡

Условие

Слова марсианского языка состоят из малых латинских букв. Буквы a, e, i, o, u, y считаются гласными, остальные — согласными.

Дифтонгом называется пара подряд идущих гласных букв, окружённых либо согласными буквами, либо границами слова. Например, в слове preemptio имеется два дифтонга, а в слове aaa — ни одного.

Требуется среди N данных слов найти те, в которых количество дифтонгов максимально.

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

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

Ограничения

1 ≤ N ≤ 100

Слова содержат от 1 до 255 символов.

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

3
e
ee
eee

ee

3
aabbee
cyydyyy
xiixiixiii

aabbee
xiixiixiii

Задача O. Усовершенствованный шифр Цезаря ≡

Условие

Требуется написать программу для преобразования строки S в строку H в соответствии с правилом: символ строки H с номером i равен соответствующему символу строки S, смещённому на i символов по алфавиту (символы в строке нумеруются с 1; символ 'Z', смещённый на 1 символ, равен символу 'A').

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

Входной файл содержит строку S, состоящую из заглавных букв английского языка.

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

Выходной файл должен содержать строку H — закодированное сообщение.

Ограничения

Строка во входном файле содержит от 1 до 255 символов.

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

AAAAAAAAAAAAAAAAAAAAAAAAAAAA

BCDEFGHIJKLMNOPQRSTUVWXYZABC

QWERTY

RYHVYE

Задача P. Количество битов в числе ≡

Условие

Дано целое неотрицательное число x, требуется посчитать количество не нулевых битов в числе.

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

Первая строка входного файла содержит число x.

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

Входной файл должен содержать одно число  — количество не нулевых битов в числе x.

Ограничения

0 ≤ x ≤ 2 ⋅ 10⁹

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

1

1

15

4

Задача Q. K-й бит в числе ≡

Условие

Дано целое неотрицательное число x, требуется вернуть значение k-го бита числа x, то есть k-й разряд двоичного представления числа x. Разряды нумеруются с 0 начиная с младшего. Считается что число содержит неограниченное количество лидирующих нулей.

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

Первая строка входного файла содержит два числа x, k.

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

Входной файл должен содержать одно число  — значение k-го бита числа x.

Ограничения

0 ≤ x ≤ 2 ⋅ 10⁹

0 ≤ k ≤ 300

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

0 10

0

123 0

1

12345 100

0

Задача R. Единственный канал у пикселя ≡

Условие

Витя, Петя и Олег — программисты. Они решили написать свой графический редактор на библиотеке Qt!

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

Петя и Олег знают, что цвет пикселя обычно кодируется тремя значениями — red, green, blue. Каждый в диапазоне от 0 до 255. Но модуль Вити возвращает цвет пикселя в виде единственного числа. В битах с 0 по 7 включительно отражена интенсивность синего канала. С 8 по 15 зелёного, а с 16 по 23 интенсивность красного.

Разработчикам нужно не много — оставить только один цветовой канал и вернуть полученный цвет в том же формате. К сожалению, Петя и Олег проспали лекцию по битовому представлению чисел в памяти компьютера, и теперь им нужна ваша помощь.

На вход подаётся число, и буква r\g\b — канал, который нужно оставить. Ваша задача получить итоговый цвет в том же формате.

Формат входных данных

Входные данные содержат число n и символ m — значение цвета и необходимый канал.

Формат выходных данных

Выходные данные должны содержать единственное число — цвет в числовом представлении.

Ограничения

0 ≤ n ≤ 16777215

m ∈ {′r′, ′g′, ′b′}

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

6579300 g

25600

Задача S. Битовый диктатор ≡

Условие

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

Возьми число a, подели нацело его на 4 (2²), далее умножь на 16 (2⁴), после этого сделай побитовое "ИСКЛЮЧАЮЩЕ ИЛИ" с числом b, получившийся результат умножь на 2 (2¹), и сделай побитовое "ИЛИ" с числом c. Ответом будет побитовое "И" уже получившегося результата и числа 1073741823.

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

Первая строка входного файла содержит три числа a, b и c.

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

Входной файл должен содержать одно число — значение результат формулы.

Ограничения

0 ≤ a, b, c ≤ 2 ⋅ 10⁵

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

0 10 25

29

123 123 123

895

Задача T. Сеть Фейстеля ≡

Условие

Необходимо реализовать шифрование Сетью Фейстеля

Псевдокод шифрования:

    
      for i in range(blocks):
          for r in range(rounds):
              TEMP = L[i]
              L[i] = R[i]
              R[i] = TEMP XOR F(K[r], R[i])
      
  

L[i] - первая половина i-го блока

R[i] - вторая половина i-го блока

K[r] - ключ шифрования на r-ом раунде, в данной задаче размер ключа равен размеру половины блока

F - функция шифрования, в данной задаче используется XOR

В случае если длина строки не кратна размеру блока, строка дополняется символами '\0'

Половины блока имеют одинаковую длину

Длина блока всегда четная

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

Первая строка входного файла содержит количество тестов N

Первая строка теста: 2 целых числа - количество раундов, размер блока в байтах

Вторая строка теста: раундовые ключи шифрования одной HEX строкой

Третья строка теста: целевая ASCII строка, которую необходимо зашифровать

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

Выходной файл должен содержать N строк - шифротекстов HEX-ом для каждой целевой строки

Ограничения

Длина строки <= 65536

Размер блока <= 64

Кол-во раундов <= 32

Кол-во тестов <= 335

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

1
2 4
90A314CE
Phad1d2Ref

A1AFD4059395B509F5C5E10B

Задача U. Честная очередь ≡

Условие

В одном из травмпунктов города Владивостока прием пациентов осуществляется по следующим правилам:

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

Обычно во все кабинеты имеется очередь. Некоторые люди, если им надо попасть сразу в два кабинета, занимают две очереди, а остальные — сначала проходят рентген, а потом занимают очередь в кабинет вторичного приема.

Если к моменту, когда пациент, занявший обе очереди, выходит из рентгеновского кабинета, его очередь на вторичный осмотр уже прошла, то он становится в конец этой очереди. Если пациент выходит из рентгеновского кабинета в ту же минуту, что начинается его очередь на вторичный осмотр, то считается, что он её пропустил (см. пример 2).

По заданной последовательности появления пациентов выясните время, которое понадобится каждому из пациентов, чтобы посетить все назначенные ему кабинеты. При этом следует считать, что для любого пациента длительность приема в кабинете рентгенографии равна P минут, длительность приема в кабинете второго осмотра равна Q минут, а время первичного приёма равно нулю.

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

Входной файл содержит числа N P Q, за которыми следуют N наборов чисел.

В каждом наборе первое число означает время прихода пациента t_i, измеренное в минутах с начала приема. Далее идет число, обозначающее, в какие кабинеты требуется попасть i-му пациенту — 1, если сперва в кабинет рентгенографии и 2, если сразу в кабинет вторичного приема.

Для пациентов, которым требуется сделать снимок, далее идет число 1 или 2, обозначающее, займет ли пациент он место в одной очереди или в двух.

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

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

Ограничения

1 ≤ N ≤ 100, 1 ≤ P, Q ≤ 15, 0 ≤ t_i ≤ 1000, t_i < t_i + 1

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

2 5 10
0 1 1
5 1 1

15 20

2 5 5
0 1 1
5 2  

15 5

3 5 10 0 1 2 2 2 3 2

32 10 19

Задача V. Заколдованный аквариум ≡

Условие

По мотивам романа А. и Б. Стругацких “Понедельник начинается в субботу”.

Очередной понедельник выдался в НИИЧАВО (Научно-Исследовательский Институт ЧАродейства и ВОлшебства) на удивление беспокойным. Началось все с проблем в отделе исследования живой, мёртвой и водопроводной воды, куда на прошлой неделе завезли новый аквариум. Туда и вошел Привалов в самый интересный момент беседы между Амвросием Амбруазовичем Выбегалло и заведующим отделом смысла жизни Кристобалем Хозевичем Хунтой. Сейчас Кристобаль Хозевич в красках описывал, какие могут возникнуть повреждения всей новейшей системы безопасности, недавно установленной в институте, от всего того количества воды, которым сейчас затапливался его отдел.

 — Подождите, остановил его речь Выбегалло, вот закончим проверку и выключим воду.

 — Да какая же это проверка, это же чистой воды саботаж! — возмущался Хунта, вот сейчас заделаю все дырки в вашем аквариуме, и тогда будем разговаривать.

 — Нет, это категорически невозможно! — Возражал Выбегалло, — как вы себе это представляете? Мы проводим важнейший эксперимент!

 — Может быть, объясните, что здесь все-таки происходит? - вмешался в разговор Привалов

 — Позвольте, я объясню, начал было Выбегалло, но Кристобаль Хозевич не дал ему закончить, и, сделав руками несколько пассов, произнес, — вот теперь порядок, ничего не вливается и не выливается, можете объяснять.

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

Привалов, наконец, осмотрел новый аквариум. Он представлял собой прямоугольный параллелепипед размерами W × H × L метров без верхней крышки, на лицевой стороне которого было вырезано N квадратных отверстий c длиной стороны a_i метров. Сверху над аквариумом висела большая труба, через которую в него поступало M кубических метров воды в секунду.

 — Так вот, — продолжил Выбегалло, — до появления здесь Кристобаля Хозевича мы проводили эксперимент, целью которого было определить уровень воды в этом аквариуме при заданной конфигурации отверстий.

 — А более сухого способа вы не нашли, — вставил свою реплику Хунта

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

 — Замечательная идея, молодой человек, — произнес Выбегалло, — это ж сколько средств то можно сэкономить, да и воду тратить не придется.

Через несколько минут он передал Привалову формулу расчета потока воды из отверстий в аквариуме. Поскольку аквариум до эксперимента был специально заколдован, формула была оказалась простой: через отверстие площадью b квадратных метров в одну секунду будет вытекать V × b кубических метров воды.

В начале эксперимента аквариум пуст. Через некоторое время после того, как из трубы начнёт поступать вода, уровень в воды в аквариуме стабилизируется (либо аквариум переполнится). Теперь осталось только написать программу, определяющую высоту стабильного уровня воды.

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

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

Ограничения

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

1 4 3
1.0 1.0 4.0
6.0 2.0 4.0
11 5.0 3.0

2.0

Задача W. Дипломы ≡

Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

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

Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.

Система оценивания

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

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

Входной файл содержит три целых числа: W, H, N

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

В выходной файл необходимо вывести ответ на поставленную задачу.

Ограничения

1 ≤ W, H, N ≤ 10⁹

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

2 3 10

9

Problem X. Square sort ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 4 3 10 3 1

1 3 3 4 10

Problem Y. Lin-log sort ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 4 3 10 3 1

1 3 3 4 10

Задача Z. k-я порядковая статистика ≡

Условие

K-й порядковой статистикой N-элементного массива называется число А_k, которое будет стоять на K-м месте после сортировки этого массива по возрастанию.

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

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

Ограничения

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

3 2 
2 3 1

2

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

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10⁶

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

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

3
5 1 10

5 1 10

8
4 7 8 7 4 8 7 4

7 4 8

16
17 88 39 88 17 39 88 17 88 17 39 39 17 39 17 222222222

17 39 88 222222222