1415. 查询最值

维护一个长度为 nn 的序列 aa,实现下面的操作:

1 k: 删除第 kk 个数。右边的数全部往左移动一位(下标减一)。

2 l r: 查询 minlirai\min_{l \leq i \leq r}a_imaxlirai\max_{l \leq i \leq r}a_i

保证查询时序列非空且 k,l,rk,l,r 合法。

输入

第一行两个整数 n,q (1n,q2×105)n, q \ (1 \leq n,q \leq 2 \times 10^5),表示序列长度和操作个数。

第二行包括 nn 个数 a1,a2,...,an (1ai109)a_1,a_2,...,a_n \ (1 \leq a_i \leq 10^9),表示原始序列。

接下来 qq 行,每行格式为 1 k 或者 2 l r,表示询问。

输出

对每个查询操作输出一行,包括两个数,表示最小值和最大值。

样例

标准输入 复制文本
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
登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 89
通过 9