题目描述

有一个包含 $n$ 个元素的数组，要求实现以下操作：

• DELETE k：删除位置 $k$ 上的数。右边的数往左移一个位置。
• QUERY i j：查询位置 $i\sim j$ 上所有数的最小值和最大值。

例如有 $10$ 个元素：

QUERY 2 8 的结果为 2 9。依次执行 DELETE 3 和 DELETE 6（注意这时删除的是原始数组的元素 $7$）后数组变为：

QUERY 2 8 的结果为 1 7。

输入格式

第一行包含两个数 $n,m$，表示原始数组的元素个数和操作的个数。
第二行包括 $n$ 个数，表示原始数组。
以下 $m$ 行，每行格式为 1 k 或者 2 i j，其中第一个数为 $1$ 表示删除操作，为 $2$ 表示询问操作。

输出格式

对每个询问操作输出一行，包括两个数，表示该范围内的最小值和最大值。

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

提示

对于 $50\%$ 的数据，$1 \le n, m \le {10}^4$，删除操作不超过 $100$ 个。
对于 $100\%$ 的数据，$1 \le n, m \le {10}^6$，数组中的元素绝对值均不超过 ${10}^9$。