动态最值

动态最值

Description

有一个包含 \(n\) 个元素的数组,要求实现以下操作:
delete k:删除位置 \(k\) 上的数,且右边的数往左移一个位置。
query i j:查询位置 \([i,j]\) 上所有数的最小值和最大值。

Input

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

Output

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

Sample Input

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

Sample Output

2 9
1 7

Limitation

1s, 1024KiB for each test case.

Hint

100%的数据满足 \(1\le n, m \le 10^6\)
100%的数据,数组中的元素绝对值均不超过 \(10^9\)

Source

SCOI 2006

信息

ID
1003
难度
4
分类
(无)
标签
(无)
递交数
6
已通过
2
通过率
33%
上传者

相关

在下列比赛中:

练习赛2

练习赛1