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

Условие

Пусть задан массив из 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 ≤ 2n − 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

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

Условие

Дана последовательность из 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 C. Caterpillar ≡

Statement

A caterpillar of length L crawls over rough terrain. Rough terrain can be represented as a one-dimensional array of N cells with different heights. A cell a_i is called a downhill if a_i > a_i + 1. A cell a_i is called an uphill if a_i < a_i + 1. Initially, the caterpillar occupies the first L cells.

In order to advance one cell, the caterpillar spends 1 second of time. However, if it occupies more downhills than uphills, and the head of the caterpillar is on the downhill, it immediately moves one cell to the right.

Determine after how many seconds the head of the caterpillar reaches the last cell.

Input format

The first line of the input file contains two integers L, N. The second line contains N integers a_i.

Output format

The output must contain one integer — time after which the caterpillar reaches the last cell.

Constraints

1 ≤ a_i, N, L ≤ 10⁶, L ≤ N, a_i ≠ a_i + 1

Sample tests

1 4
4 3 2 3

1

3 10
10 9 8 7 8 9 10 9 8 7

4

Задача D. Чемпионат по боксу ≡

Условие

В чемпионате по боксу соревнуется две команды по N боксёров в каждой. Все боксёры разбиты на M весовых категорий. Каждый боксёр характеризуется уровнем мастерства p_i (при этом не существует двух боксёров с равным уровнем мастерства) и номером весовой категории в которой он выступает c_i. Чемпиона проходит по следующим правилам: все участники разбиваются по весовым категориям и в рамках одной весовой категории каждый боксёр одной команды выходит на ринг против каждого боксёра другой команды, за победу в бое начисляется одно очко. Боксёр точно победит если его уровень мастерства выше уровня мастерства соперника.

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

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

Первая строка входного файла содержит два целых числа N, M. Далее N пар чисел p_i, с_i  — описание боксёров из команды Пахома. Далее N пар чисел p_i, с_i  — описание команды соперников.

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

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

Ограничения

1 ≤ N ≤ 10⁶, 1 ≤ M ≤ 300, 1 ≤ с_i ≤ M; 1 ≤ p_i ≤ 10⁹.

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

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

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

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

-9

4 2
60 1
100 2
110 2
120 2
200 1
50 2
40 2
30 2

12

3 3
5 1
10 2
15 3
6 1
11 2
16 3

-1

Problem E. 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