Description

One day, Xiao Cheng had just obtained a strange meteorite sample from the institute, and he could not wait to start observing it. Under the view of precise instruments, every atom that made up the meteorite was extremely clear.

Xiao Cheng found that these atoms were arranged into several columns, and the structure of each column was highly similar. Therefore, he decided to measure and test a single column of atoms.

The chosen column contains $N$ atoms arranged in order. Initially, the $i$-th atom has energy $E_i$. As time passes and due to manual tests, this column of atoms will undergo two kinds of observable changes:

• merge x e: merge the current $x$-th atom and the $(x + 1)$-th atom, obtaining a new atom with energy $e$;
• insert x e: insert a new atom with energy $e$ between the current $x$-th atom and the $(x + 1)$-th atom.

For a column of atoms, what Xiao Cheng cares about is the energy difference between the atoms with the maximum energy and the minimum energy in a contiguous segment, which is called the interval range. Therefore, besides observing the changes, Xiao Cheng also often needs to compute two kinds of statistics on this column of atoms:

• max x y: the maximum value of the interval range over all subintervals within the current atoms from position $x$ to position $y$;
• min x y: the minimum value of the interval range over all subintervals within the current atoms from position $x$ to position $y$.

Here, a subinterval means a contiguous segment with length at least $2$.

Xiao Cheng firmly believes this research can win the Nobel Prize in Physics. To help Xiao Cheng fulfill his wish as soon as possible, can you help him implement the above observations and measurements?

Input Format

The first line contains two integers $N, M$, representing the initial number of atoms and the total number of events.

The second line contains $N$ integers $E_1, E_2, ..., E_N$ separated by spaces, representing the energy of each atom in order.

The next $M$ lines each contain a string and two integers, describing one event. The format is the same as in the problem description.

Output Format

Output several lines. In order, each line should be the result for each max and min event.

4 3
5 8 10 2
max 1 3
min 1 3
max 2 4

5
2
8

Hint

Constraints

For $100\%$ of the testdata, $1 \le N \le 10^5$, $1 \le M \le 10^5$, $1 \le e, E_i \le 10^9$.

Let $N'$ be the current number of atoms:

• For merge events, $1 \le x \le N' - 1$.
• For insert events, $1 \le x \le N'$.
• For max and min events, $1 \le x < y \le N'$.

At any time, it is guaranteed that $N' \ge 2$.

Translated by ChatGPT 5