Юниорская олимпиада по информатике 2022 года за 7 класс | Казахстанские олимпиады

Задача B. How You Like That

Дано $N$ солдатиков которые стоят в одном ряду, массив $A$ длиной $N$ рост каждого солдата (все числа различные). Также дано $Q$ запросов и каждый запрос состоит из трёх значении $I$ - номер солдата, $Dir$ - сторона куда смотрит солдат в текущий момент ($L$ - на лево, $R$ - на право) и число $K$, для каждого солдата нужно найти K-й номер солдата которого он сможет увидит, либо выведите -1 если такого нету.

Обратите внимание если наш массив состоит из чисел [1, $4$, $5$, $2$, $3$, $6$, 7], то солдат под номером $1$ может видит только солдат под номером $2$, $3$, $6$, $7$. Как вы могли заметить солдатов под номером $4$, $5$ не видно из-за того что они стоят после солдата под номером $3$ (рост солдата $3$ выше роста солдатов $4$, $5$ и закрывает обзор).

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

В первой строке входных данных записаны два числа $N$ и $Q$ ($1$ $\le$ $N$ $\le$ 10^5, $1$ $\le$ $Q$ $\le$ 10^6) — количество солдат и количество запросов.

В второй строке входных данных записан массив $A$ ($1$ $\le$ $A_i$ $\le$ 10^9) — рост каждого солдата.

В следующих $Q$ строках записаны запросы $I$, $Dir$, $K$ ($1$ $\le$ $I$, $K$ $\le$ $N$) — описание каждого запроса.

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

Выведите ответ на задачу.

Примеры

Входные данные

5 3
1 4 2 3 5
1 R 3
3 L 1
4 L 2

Выходные данные

-1
2
-1

Входные данные

7 4
1 4 5 2 3 6 7
1 R 3
3 L 1
4 R 2
6 L 1

Выходные данные

6
-1
6
-1