P1110 [ZJOI2007] Report Statistics

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?

- 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).

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

#### 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