Description

Little Q’s mother is a cashier and often needs to prepare statistical reports. Today is her birthday, and Little Q wants to help with some of the work as a birthday present.

After careful observation, Little Q finds that preparing a report is essentially maintaining a sequence of non-negative integers and performing some queries.

Initially, there is an integer sequence $a$ of length $n$, and the following three operations are supported:

• INSERT i k: Append a new element $k$ immediately after the $i$-th element of the original sequence. If some elements have already been appended after the $i$-th original element, append $k$ after all those appended elements (see the sample explanation).
• MIN_GAP: Query the minimum absolute difference between any two adjacent elements.
• MIN_SORT_GAP: Query the minimum absolute difference between the two closest elements among all elements.

Little Q wrote a program to automate these operations, but it runs slowly on large reports. Can you help improve it?

Input Format

• The first line contains two integers, the length $n$ of the original sequence and the number of operations $m$.
• The second line contains $n$ integers, the initial sequence; the $i$-th integer is $a_i$.
• The next $m$ lines each contain one operation, which is one of INSERT i k, MIN_GAP, or MIN_SORT_GAP (no extra spaces or blank lines).

Output Format

For each MIN_GAP and MIN_SORT_GAP command, output the answer on its own line.

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

2
2
1

Hint

Explanation of Sample Input/Output 1

The initial sequence is $\{5,3,1\}$.

After performing INSERT 2 9, the sequence becomes $\{5,3,9,1\}$. At this time, MIN_GAP is $2$, and MIN_SORT_GAP is $2$.

Next, performing INSERT 2 6 yields $\{5,3,9,6,1\}$.

Note that by this time one $9$ has already been appended after the 2nd element of the original sequence, so the newly inserted $6$ should be placed after $9$. Now MIN_GAP is $2$, and MIN_SORT_GAP is $1$.

Constraints

For all test points, it is guaranteed that $2 \le n, m \le 5 \times 10^5$, $1 \le i \le n$, and $0 \le a_i, k \le 5 \times 10^8$.

Translated by ChatGPT 5