케이크

레오폴드와 몰리는 케이크를 좋아한다. 레오폴드는 케이크를 먹는 쪽을 좋아하고, 몰리는 레오폴드가 케이크를 먹는 모습을 보는 쪽을 좋아한다. 오늘 두 사람은 케이크 조각 $N$개를 샀다. 조각은 자리가 $N$개인 좁고 긴 접시 위에 한 줄로 놓여 있다. 자리에는 왼쪽부터 $1$번부터 $N$번까지 번호가 붙어 있고, 조각 $i$는 자리 $i$에 있다.

레오폴드는 조각이 얼마나 맛있는지를 따져 가며 먹는다. 조각 $i$의 처음 맛 값은 $d_i$다. 레오폴드는 조각 $a$를 가장 먼저 먹고, 그러면 자리 $a$가 빈다. 그다음부터는 빈 자리와 이웃한 조각 중 가장 덜 맛있는 조각을 먹는다. 그래서 빈 자리는 언제나 닫힌 구간 하나를 이룬다. 몰리는 가끔 어떤 조각에 토핑을 올려 그 조각을 더 맛있게 만든다. 몰리는 토핑을 올린 조각이 항상 가장 맛있는 조각 10개 안에 들도록 한다. 어느 시점에도 맛 값이 같은 조각은 없다.

몰리는 토핑을 더 올리지 않는다고 할 때 레오폴드가 조각 $b$를 먹기 전에 조각을 몇 개나 먹는지 궁금해할 때가 있다. 조각을 더 맛있게 만드는 명령과, 어떤 조각보다 먼저 먹는 조각의 개수를 묻는 명령을 처리하는 프로그램을 작성하라.

질의는 케이크를 실제로 먹어 없애지 않는다. 각 질의는 그 시점의 맛 값을 그대로 두고 조각 $a$부터 다시 시작하는 먹기 과정을 가정한다.

첫째 줄에 조각의 개수 $N$ ($1 \le N \le 250\,000$)과 레오폴드가 가장 먼저 먹는 조각의 번호 $a$ ($1 \le a \le N$)가 주어진다. 둘째 줄에 조각의 처음 맛 값 $d_1, \dots, d_N$이 주어진다. 이 값은 모두 다르고 $1 \le d_i \le N$을 만족한다. 셋째 줄에 처리할 명령의 개수 $Q$ ($1 \le Q \le 500\,000$)가 주어진다. 다음 $Q$개 줄에는 아래 두 가지 중 한 형태의 명령이 주어진다.

• E i e (문자 E 다음에 두 정수 $1 \le i \le N$, $1 \le e \le 10$): 조각 $i$에 토핑을 올려 그 조각이 $e$번째로 맛있는 조각이 된다. 나머지 조각 사이의 맛 순서는 바뀌지 않는다. 토핑을 올리기 전에 조각 $i$보다 맛있는 조각은 $e$개 이상임이 보장된다.
• F b (문자 F 다음에 정수 $1 \le b \le N$): 레오폴드가 조각 $b$를 먹기 전에 먹는 조각의 개수를 묻는다.

F 명령마다 입력에 나온 순서대로 한 줄씩, 물어본 조각의 개수를 정수 하나로 출력한다.

• $N \le 250\,000$, $Q \le 500\,000$