Ancient Mountain Range

An ancient mountain range is represented as a sequence of mountain elements, where each element has a height. Initially, the mountain (denoted as mountain 0) is empty. Mountains are built by performing operations, and each operation creates a new mountain with a sequential number. The mountain elements in any mountain are numbered from 1 (from left to right).

There are three types of operations:

1. I h x: Insert a mountain element with height h to the right of the x-th mountain element in the current mountain. (Note: if x is 0, insert at the beginning.)
2. R l r: Reverse the segment from the l-th to the r-th mountain element in the current mountain. For example, given elements \(a_1,a_2,a_3,a_4,a_5\), reversing the segment \((2,5)\) results in \(a_1,a_5,a_4,a_3,a_2\).
3. M t x: Insert a copy of mountain t (i.e. its entire sequence of elements) to the right of the x-th element of the current mountain.

After any operation, if the current mountain is the \(i\)-th mountain, the new mountain becomes the \((i+1)\)-th mountain.

The key query in this problem is to compute the energy collected by a submountain. For a queried submountain consisting of the elements from position \(l\) to \(r\):

1. Let \(h_i\) denote the height of the \(i\)-th element in the submountain.
2. Let \(x\) be the position (in the full mountain) of the highest mountain element within \([l, r]\). If there are \(m\) elements with the same maximum height, choose the left \(\lceil m/2 \rceil\)-th occurrence in the submountain.
3. The energy is then defined as: \[ Energy = \sum_{i=l}^{x-1} \begin{cases} x-i, &\text{if } h_i > h_{i+1}\\ 0, &\text{otherwise} \end{cases} + \sum_{i=x+1}^{r} \begin{cases} i-x, &\text{if } h_i > h_{i-1}\\ 0, &\text{otherwise} \end{cases}. \]

The queries are given in the form:

• Q l r: Query the energy collected by the submountain formed by the mountain elements from position \(l\) to \(r\) of the current mountain.

Input/Output Note: The operations and queries are performed in order. Operations (I, R, M) modify the current mountain state by producing a new mountain, while query operations (Q) do not change the current mountain.

inputFormat

The first line contains an integer \(n\) representing the number of commands. The following \(n\) lines each contain a command. Each command is in one of the following forms:

• I h x: Insert a mountain element with height \(h\) to the right of the \(x\)-th element of the current mountain. (\(x = 0\) means insert at the beginning.)
• R l r: Reverse the subarray from position \(l\) to \(r\) (inclusive) of the current mountain.
• M t x: Insert a copy of mountain \(t\) (its entire element sequence) to the right of the \(x\)-th element of the current mountain. You can assume that mountain \(t\) has been created before.
• Q l r: Query the energy of the submountain consisting of elements from position \(l\) to \(r\) in the current mountain.

Initially, mountain 0 is empty, and the current mountain is always the latest created mountain (from the last operation of type I, R, or M). Query operations do not change the current mountain.

outputFormat

For each query command (Q l r), output the energy value of the corresponding submountain on a new line.

sample

9
I 5 0
I 3 1
I 7 2
Q 1 3
R 1 3
Q 1 3
M 2 2
Q 2 5
Q 1 5

2
2
2
6

</p>