메뚜기의 점프

N마리의 메뚜기가 공연을 보려고 한 줄로 서 있다. 기다리는 동안 지루해진 메뚜기들은 다음 두 가지 행동 중 하나를 한다.

• 현재 A번째 위치에 있는 메뚜기가 왼쪽에 있는 B마리의 메뚜기를 뛰어넘는다.
• 현재 A번째 위치에 있는 메뚜기가 오른쪽에 있는 B마리의 메뚜기를 뛰어넘는다.

메뚜기들의 키는 서로 다를 수 있다. 어떤 메뚜기가 다른 메뚜기들을 뛰어넘을 때에는 다리에 부딪히지 않도록, 뛰어넘는 메뚜기들 중 가장 키가 큰 메뚜기의 키만큼 높이 뛰어야 한다.

점프가 일어나는 순서가 주어질 때, 각 점프에 필요한 높이를 차례대로 출력하라.

첫째 줄에 줄에 선 메뚜기의 수 N과 점프의 수 J가 주어진다. (2 <= N <= 100000, 1 <= J <= 100000)

둘째 줄에는 처음 줄에서의 순서대로 메뚜기 N마리의 키가 주어진다. 각 키는 100000보다 작은 정수이다. 처음에는 첫 번째 메뚜기가 1번 위치, 두 번째 메뚜기가 2번 위치에 서 있는 식이다.

다음 J개의 줄에는 점프 하나가 순서대로 주어진다. 각 줄은 정수 A, 문자 방향, 정수 B로 이루어진다. A는 점프하는 메뚜기의 현재 위치이며 1 <= A <= N이다. 방향은 왼쪽을 뜻하는 'L' 또는 오른쪽을 뜻하는 'D'이다. B는 뛰어넘는 메뚜기의 수이며 1 <= B <= N이다.

모든 점프는 항상 가능하게 주어진다. 즉, B는 점프하는 방향 쪽에 실제로 있는 메뚜기의 수 이하이다.

점프가 일어나는 순서대로 각 점프에 필요한 높이를 한 줄에 하나씩 출력한다.

첫 번째 점프에서는 키가 8, 4, 9인 메뚜기들을 뛰어넘으므로 필요한 높이는 9이다. 두 번째 점프에서는 키가 3, 7인 메뚜기들을 뛰어넘고, 마지막 점프에서는 키가 3, 4인 메뚜기들을 뛰어넘는다.