P6011 [SCOI2006] Dynamic Min/Max

You are given an array containing $n$ elements. You need to support the following operations: - `DELETE k`: Delete the number at position $k$. All numbers to the right shift one position to the left. - `QUERY i j`: Query the minimum and maximum values among all numbers in positions $i \sim j$. For example, there are $10$ elements: | Position | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | | Element | $1$ | $5$ | $2$ | $6$ | $7$ | $4$ | $9$ | $3$ | $1$ | $5$ | The result of `QUERY 2 8` is `2 9`. After performing `DELETE 3` and then `DELETE 6` (note that this deletes the element $7$ from the original array), the array becomes: | Position | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | | Element | $1$ | $5$ | $6$ | $7$ | $4$ | $3$ | $1$ | $5$ | The result of `QUERY 2 8` is `1 7`.

The first line contains two integers $n, m$, representing the number of elements in the original array and the number of operations. The second line contains $n$ integers, representing the original array. The next $m$ lines each describe an operation in the form `1 k` or `2 i j`, where the first number is $1$ for a delete operation, and $2$ for a query operation.

For each query operation, output one line containing two integers: the minimum value and the maximum value in that range.

For $50\%$ of the testdata, $1 \le n, m \le {10}^4$, and there are no more than $100$ delete operations. For $100\%$ of the testdata, $1 \le n, m \le {10}^6$, and the absolute value of each array element does not exceed ${10}^9$. Translated by ChatGPT 5