Задача 1E. Пошаговые утки ≡

Условие

Даки и Утя играют в пошаговую игру, для выбора свой стратегии Даки нужна программа. У них есть поле размера n * 1, в каждой ячейке которой находится предмет стоимостью a_i монет. Чтобы выбрать, что делать дальше Даки после каждого хода анализирует предмет какой максимальный стоимости находится между ним и Утей.

Изначально Даки и Утя находятся на первой клетке поля. А дальше, в сумме делают m шагов. Каждый шаг: L - ход Ути, R - ход Даки. Гарантируется, что Утя никогда не перегонит Даки.

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

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

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

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

В выходной файл выведите в одну строку ровно m чисел, где i-е число — максимальная стоимость предмета на отрезке от Ути до Даки после 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