Problem Description

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:

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:

The result of QUERY 2 8 is 1 7.

Input Format

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.

Output Format

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

10 4
1 5 2 6 7 4 9 3 1 5
2 2 8
1 3
1 6
2 2 8

2 9
1 7

Hint

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