Задача A. Ближайшее число ≡

Условие

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

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

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

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

В выходной файл необходимо вывести N целых чисел b_i, таких что b_i является ответом на задачу для числа a_i.

Ограничения

1 ≤ N ≤ 10⁶

|a_i| ≤ 10⁹

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

4 1 2 3 4

2 3 4 4

1
1

1

Problem B. Altitude and visibility ≡

Statement

Consider a sequence of numbers a₁, …, a_N, representing heights. Let's say that element a_i has a visibility radius d if a_i ≥ a_j for all j such that 1 ≤ j ≤ N and |i − j| < d.

You task is to find maximum d_i for every a_i.

Input file format

Input file contains integer N followed by N integers a_i.

Output file format

Output file must contain N integers d_i — maximum visibility for every a_i. If maximum visibility radius for element a_i is unlimited, output d_i = 0.

Constraints

1 ≤ N ≤ 10⁶, 0 ≤ a_i ≤ 10⁹

Sample tests

1
10

0 

6
1 5 2 2 1 4

1 0 1 2 1 4 

Задача C. Максимум в скользящем окне ≡

Условие

Пусть задан массив из n целых чисел. По этому массиву будут ходить два указателя l и r. Изначально оба они указывают на первый элемент массива. Оба указателя могут двигаться только вправо, на одну позицию за раз. При этом указатель l никогда не оказывается правее указателя r, и ни один из них не выходит за пределы массива. Вам нужно после каждого перемещения указателя определить максимум всех элементов от указателя l вправо до указателя r (включая позиции, на которые указывают l и r).

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

Первая строка входного файла содержит целое число n - размер массива. Во второй строке содержится строке n целых чисел a_i - сам массив.

В третьей строке указано число m — количество перемещений. В четвертой строке — m символов 'L' или 'R', разделенных пробелами. 'L' означает, что нужно сдвинуть l вправо, 'R' — что нужно сдвинуть r вправо.

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

В выходной файл выведите в одну строку ровно m чисел, где i-е число — максимальное значение на отрезке от l до r после выполнения i-й операции.

Ограничения

1 ≤ n ≤ 10⁵

|a_i| ≤ 10⁹

0 ≤ m ≤ 2 n − 2

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

4
-3 -2 -1 0
6
RRRLLL

-2 -1 0 0 0 0

10
1 4 2 3 5 8 6 7 9 10
12
RRLRRRLLLRLL

4 4 4 4 5 8 8 8 8 8 8 6

Задача D. Сбалансированное дерево revisited ≡

Условие

Дана последовательность целых чисел. Каждое прочитанное число обрабатывается следующим образом:

• если число больше нуля, оно добавляется к текущему множеству чисел;
• если число меньше нуля, противоположное ему число удаляется из текущего множества чисел;
• если число равно нулю, множество чисел выводится в порядке возрастания и программа завершает работу.

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

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

Ограничения

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

3 2 1 3 0

1 2 3

5 -1 6 -5 5 0

5 6

Задача E. Золотая середина ≡

Условие

Центральным элементом набора из k чисел называется такой элемент, который после сортировки набора будет занимать в нём центральную позицию (то есть позицию номер ⌈k / 2⌉, считая с единицы).

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁶,  − 10⁹ ≤ a_i ≤ 10⁹.

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

3
5 3 4

5 3 4

5
1 2 3 2 4

1 1 2 2 2