Задача 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

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

Условие

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

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

Задача D. Мёд и справедливость ≡

Условие

Две пчелы собирают пыльцу с N цветков, расположенных в ряд. Цветок номер i содержит a_i микрограмм пыльцы.

Пчёлы договорились, что первая пчела будет собирать пыльцу с цветков на участке от L до M включительно, а вторая  — от M + 1 до R включительно (L ≤ M < R). Чтобы ни одной из пчёл не было обидно, сумма запасов пыльцы на первом и втором участках пчёл должны совпадать.

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

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

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

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

Выходные данные должны содержать целые числа L M R — границы участков. Если оптимальных решений несколько, выведите решение с наименьшим значением L. Если решения не существует, выведите единственное число  − 1.

Ограничения

2 ≤ N ≤ 10000

1 ≤ a_i ≤ 10⁵

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

3
1 1 2

1 2 3

2
2 5

-1

Задача E. Слон и куб ≡

Условие

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

На внешние ячейки куба, расположенные с трёх сторон, обозначенных на рисунке цифрами 1, 2 и 3, можно нажимать. В результате нажатия числа в ячейке, на которую нажали и во всех ячейках, находящихся за ней (то есть пересекаемых прямой, проведённой через центр нажатой ячейки перпендикулярно стороне куба), увеличиваются на 1.

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

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

Оси координат расположены, как показано на рисунке. Координаты по каждой оси отсчитываются начиная с 1 в направлении, указанном стрелкой.

Описание нажатия на ячейку состоит из номера стороны куба, на которой она расположена, и двух координат: x и y для стороны 1, y и z для стороны 2, x и z для стороны 3.

Описание запроса Вилки состоит из номера стороны куба, которой параллельна плоскость среза, и координаты: z для стороны 1, x для стороны 2, для y для стороны 3. На рисунке показан срез, параллельный стороне 1 с координатой z = 2.

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

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

Если Q_i = 1, то это описание нажатия ячейки, и далее следует целые числа n_i u_i v_i p_i — номер стороны, с которой производится нажатие, первая и вторая координаты ячейки на стороне и количество подряд идущих нажатий данной ячейки.

Если Q_i = 2, то это описание запроса суммы на срезе, и далее следуют целые числа n_i w_i — номер стороны, которой параллельна плоскость среза, и соответствующая координата.

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

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

Ограничения

1 ≤ w_i, u_i, v_i ≤ M ≤ 10³, 1 ≤ N ≤ 10⁵, 1 ≤ p_i ≤ 10, 1 ≤ Q_i ≤ 2, 1 ≤ n_i ≤ 3.

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

1 2
1 1 1 1 2
2 1 1

2

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

15
3
0

3 11
1 1 1 1 1
1 1 1 2 1
1 1 1 3 1
1 1 2 1 3
1 1 2 2 1
1 1 2 3 1
1 1 3 1 5
1 1 3 2 1
1 1 3 3 1
2 2 2
2 3 1

15
27

Задача F. Распознавание метки ≡

Условие

Приложение дополненной реальности пытается найти на изображении, полученном с камеры телефона, метку, представляющую собой ярко раскрашенный прямоугольник. Благодаря контрастному цвету прямоугольника на этапе предварительной обработки изображение удалось преобразовать в массив из W на H элементов, каждый из которых равен либо '#' (ASCII 35), если он принадлежит прямоугольнику, либо '.' (ASCII 46) в противном случае.

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

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

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

Первая строка входного файла содержит целые числа W H N. Следующие H строк содержат по W символов . и # каждая — изображение после предварительной обработки.

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

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

Ограничения

1 ≤ W, H ≤ 100, 0 ≤ N ≤ W × H

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

Решения работающие для W, H ≤ 20 оцениваются из 50 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

3 3 1
.#.
##.
...

3

2 2 0
#.
.#

0

Задача G. Сумма не без разнообразия ≡

Условие

Задана последовательность целых чисел A₁, A₂, …, A_N. Необходимо выбрать из нее подпоследовательность из подряд стоящих чисел A_i, A_i + 1, …, A_j так, чтобы она содержала не менее K различных чисел, и сумма S = A_i + A_i + 1 + …  + A_j была максимальной.

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

Первая строка ввода содержит целые числа N и K (1 ≤ K ≤ N ≤ 200 000). Вторая строка содержит N целых чисел A₁, A₂, …, A_N (| A_i|  ≤ 1 000 000 000).

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

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

Ограничения

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

7 3
-99 1 2 -100 3 2 3

-89
2 7

3 2
1 1 1

IMPOSSIBLE