beecrowd | 1856

Arya's Death List

By Ricardo Oliveira, UFPR BR Brazil

Timelimit: 1

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.


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

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


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

Input Samples Output Samples

3 8 2
Q 3 2
I 9 8
Q 3 2
R 8
I 1 2
Q 9 1