bee 1856 - Arya's Death List

Arya: "Cersei. Walder Frey. The Mountain. Meryn Trant."

To keep her motivation, Arya always keeps in mind the list of her enemies she hates the most. The ultimate goal of her quest is to kill everyone in her list!

However, sometimes some enemy of her may be killed by someone else. When she finds out, Arya removes the enemy from her list. Also, Arya may make new enemies during her quest. When Arya makes a new enemy, she adds him to her list.

Arya wants to kill her enemies one by one, in the same order they appear in her list. At any time, she may wonder how long it will take to kill everyone between two given enemies. To do so, given two enemies a and b, she must determine how many enemies are in her list between a and b, excluding both. Help Arya by answering such questions.

Input

The first line contains an integer N (1 ≤ N ≤ 5×10⁴), the number of enemies in her initial list.

Consider that all people in the world are numbered from 1 to 10⁹, inclusive. The next line contains N integers, describing her initial list. The next line contains an integer Q (1 ≤ Q ≤ 5×10⁴), the number of operations. The next Q lines describe the operations. Each operation may be one of the following:

I p e (1 ≤ e, p ≤ 10⁹): Insert person p after enemy e in the list. It is guaranteed that e is in the list, and p is not in the list;
R e (1 ≤ e ≤ 10⁹): Remove enemy e from the list. It is guaranteed that e is in the list;
Q a b (1 ≤ a, b ≤ 10⁹): Answer how many enemies are in the list between enemies a and b, excluding both. Is is guaranteed that both a and b are in the list.

Output

Print one line for each operation of type Q with its answer.

Input Samples	Output Samples
3 3 8 2 6 Q 3 2 I 9 8 Q 3 2 R 8 I 1 2 Q 9 1	1 2 1