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

Задача C. Выбор заявок ≡

Условие

Вы прекрасно знаете, что в ЛКШ.Зима~2016 лекции читают лучшие преподаватели мира. К сожалению, лекционных аудиторий у нас не так уж и много, поэтому каждый преподаватель составил список лекций, которые он хочет прочитать ЛКШатам. Чтобы ЛКШата, утром идя на завтрак, увидели расписание лекций, необходимо его составить прямо сейчас. И без вас нам здесь не справиться.

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

В первой строке вводится натуральное число N, не более 1000 — общее количество заявок на лекции. Затем вводится N строк с описаниями заявок — по два числа в каждом s_i и f_i. Гарантируется, что s_i < f_i. Время начала и окончания лекции — натуральные числа, не превышают 1440 (в минутах с начала суток).

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

Выведите одно число — максимальное количество заявок, которые можно выполнить.

Ограничения

s_i < f_i

N ≤ 1000

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

1
5 10

1

3
1 5
2 3
3 4

2

Задача D. Cut the band ≡

Условие

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

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

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

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

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

Первая строка входного файла содержит целое число N — количество чисел на ленточке.

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

Третья строка входного файла содержит целое число M — количество друзей Васи.

Четвертая строка входного файла содержит M целых чисел b_i — нелюбимое число i-го друга. Все b_i различны.

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

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

Ограничения

1 ≤ N ≤ 10⁵

2 ≤ M ≤ 10⁵

1 ≤ a_i, b_i ≤ 10⁹

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

4
1 2 3 4
2
1 2

1

5
3 4 5 1 5
3
3 2 5

0