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

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

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 106

|ai| ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1 2 3 4
2 3 4 4
2
1
1
1

Problem B. Altitude and visibility

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

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

You task is to find maximum di for every ai.

Input file format

Input file contains integer N followed by N integers ai.

Output file format

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

Constraints

1 ≤ N ≤ 106, 0 ≤ ai ≤ 109

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1
10
0 
2
6
1 5 2 2 1 4
1 0 1 2 1 4 

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

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

|ai| ≤ 109

0 ≤ m ≤ 2 n − 2

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
-3 -2 -1 0
6
RRRLLL
-2 -1 0 0 0 0
2
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

Автор:A. Klenin   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

Выходной файл должен содержать последовательность чисел, отсортированных по возрастанию.

Ограничения

Количество чисел находится в диапазоне от 0 до 106, сами числа — в диапазоне от  − 231 до 231 − 1.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2 1 3 0
1 2 3
2
5 -1 6 -5 5 0
5 6

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

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 106,  − 109 ≤ ai ≤ 109.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
5 3 4
5 3 4
2
5
1 2 3 2 4
1 1 2 2 2

0.415s 0.012s 21