Report Statistics

Given an initial sequence of non-negative integers \(a_1, a_2, \ldots, a_n\), you are required to maintain this sequence and process several types of operations. The operations are defined as follows:

• INSERT i k: Insert a new element \(k\) immediately after the \(i\)-th element of the original sequence. If the \(i\)-th element already has previously inserted elements, append \(k\) after all of them.
• MIN_GAP: Query the minimum absolute difference between every two consecutive elements as they appear in the current sequence.
• MIN_SORT_GAP: Query the minimum absolute difference between any two elements when the current sequence is sorted in non-decreasing order.

Your task is to process a series of operations on the sequence and output the answers for the two query operations.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \le n, m \le 10^5)\), denoting the length of the initial sequence and the number of operations respectively.

The second line contains \(n\) non-negative integers \(a_1, a_2, \ldots, a_n\) representing the initial sequence.

Each of the following \(m\) lines contains an operation in one of the following formats:

• INSERT i k
• MIN_GAP
• MIN_SORT_GAP

It is guaranteed that the operation identifier and its parameters are separated by a single space.

outputFormat

For each query operation (MIN_GAP or MIN_SORT_GAP), output one integer in a separate line representing the result of that query.

sample

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

4
1
1
1