Кто громче после тебя

Ты идёшь по школьному коридору. Вдоль стены стоят N учеников, и каждый в какой-то момент говорит число (громкость, оценка, что угодно) — одно целое число.

Для каждого ученика хочется понять: кто первый справа скажет строго большее число. Если такого справа нет — значит, «никто не перекричал».

Важно: числа по модулю могут быть большими (ориентируйся на 64-битные целые, как на олимпиадах; в Python это не проблема).

Формат ввода

В первой строке дано целое число N. Во второй строке дано N целых чисел a1, a2, ..., aN.

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

Выведи N чисел через пробел. Для каждого i выведи значение первого aj справа (j > i), такого что aj > ai. Если такого j не существует — выведи -1.

Ограничения

• 2 ≤ N ≤ 65000
• -10^9 ≤ ai ≤ 10^9 (значения укладываются в 64-битный тип; на олимпиады часто так и пишут)

Пример

Ввод:

5
3 1 4 2 2

Вывод:

4 4 -1 -1 -1

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

Храните в стеке индексы таких учеников, для которых ответ пока неизвестен. Значения по этим индексам в стеке идут по невозрастанию: снизу могут быть большие, сверху — самые «слабые» кандидаты.

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

План:

• Создайте массив ответов и заполните -1.
• Идите по массиву слева направо, зная индекс i и значение x.
• Пока стек не пуст и a[st[-1]] < x, снимайте индекс p с вершины и записывайте ans[p] = x.
• После этого добавьте в стек индекс i: он будет ждать большего числа справа.
• Индексы, оставшиеся в стеке после прохода, так и имеют ответ -1.

Важно: сравнение должно быть именно строгим: a[st[-1]] < x. Равные значения не перекрикивают друг друга, поэтому при 2 и следующем 2 первый индекс нельзя снимать.

Каждый индекс добавляется в стек один раз и снимается не более одного раза. Поэтому время работы O(N), а память O(N).