题目描述

给定长度为$n$的序列$a_i$，以及$m$个询问。 询问一：1 l r，询问$\forall i\in[l,r],max{a_i}$。 询问二：2 l r，询问$\forall i\in[l,r],min{a_i}$。

输入格式

第一行输入两个整数$n,m$； 第二行输入$n$个整数$a_i$； 接下来$m$行，每行输入一个询问，格式如题面所示。

输出格式

输出共$m$行，每行一个整数，依次表示每一次询问的结果。

样例输入 #1

5 4
3 4 2 5 1
1 2 4
2 2 4
1 1 5
2 1 5

样例输出 #1

5
2
5
1

说明/提示

保证$1\leq n\leq 10^5,1\leq m\leq 10^6,0\leq a_i\leq 10^9,1\leq l\leq r\leq n$。