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

Problem D. Cut the band ≡

Statement

Young programmer Vasya came back home from an internship in a large IT company. As a souvenir, he brought back a band with a sequence of M natural numbers embroiled on it.

Vasya does not care much about numbers, so he wants to gift a band to a friend. However, each one of M Vasya's friends has exactly one number he strongly dislikes, and so would not want a band containing that number as a gift. All numbers disliked by Vasya's friends are different.

In order to still make a gift out of the band, Vasya wants to cut it in such a way, that every piece of the band could be given to at least one of his friends (several pieces may go to the same friend).

Your program must determine minimal number of cuts Vasya must perform to be able to give all pieces as gifts.

Input file format

First line of input file contains integer N — count of numbers on the band.

Second line of input file contains N integers a_i — a sequence of numbers on the band.

Third line of input file contains integer M — number of Vasya's friends.

Fourth line of input file contains M integers b_i — disliked number of i-th friend. All b_i are different.

Output file format

Output file must contain a single integer — minimal number of band cuts.

Constraints

1 ≤ N ≤ 10⁵

2 ≤ M ≤ 10⁵

1 ≤ a_i, b_i ≤ 10⁹

Sample tests

4
1 2 3 4
2
1 2

1

5
3 4 5 1 5
3
3 2 5

0