Xiao Q's mother is a cashier who often needs to prepare statistical reports. Today is her birthday, and Xiao Q hopes to help her with some of her work as a birthday gift.

After careful observation, Xiao Q discovered that preparing a report actually involves maintaining a sequence of non-negative integers and performing several query operations.

Initially, there is a sequence of integers of length $N$, and there are three types of operations:

For example, if the initial sequence is: 5 3 1

Executing the operation INSERT 2 9 results in: 5 3 9 1 At this point, MIN_GAP is 2, and MIN_SORT_GAP is 2.

Executing the operation INSERT 2 6 results in: 5 3 9 6 1 Note that at this time, a 9 has already been added after the 2nd element of the original sequence, so the newly added 6 should be placed after the 9. At this point, MIN_GAP is 2, and MIN_SORT_GAP is 1.

Xiao Q wrote a program to automatically complete these operations, but he found that his program runs very slowly for some large reports. Can you help him improve the program?

Input

The first line contains two integers $N$ and $M$, representing the length of the original sequence and the number of operations, respectively.

The second line contains $N$ integers, which is the initial sequence.

The next $M$ lines each contain an operation, which is one of INSERT i k, MIN_GAP, or MIN_SORT_GAP (with no extra spaces or empty lines).

Output

For each MIN_GAP and MIN_SORT_GAP command, output the answer on a single line.

Examples

Input 1

3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP

Output 1

2
2
1

Constraints

For 30% of the data, $N \le 1000, M \le 5000$.

For 100% of the data, $N, M \le 500000$.

For all data, the integers in the sequence do not exceed $5 \times 10^8$.