题目描述

给定一个长度为 $n$ 的不降数列，分别是$a_1,a_2,a_3,a_4,a_5……a_n$，确保数组下标为 $1-n$。

不降数列：确保对于任意的 ($2 \leq i \leq n$)，$a_{i-1} \leq a_i$恒成立

现在需要按要求进行 $q$ 次查询。规定如下 $4$ 种查询方案。

• 1 k：查找小于 $k$ 的数字中，位置最大为多少。
• 2 k：查找小于等于 $k$ 的数字中，位置最大为多少。
• 3 k：查找大于 $k$ 的数字中，位置最小为多少。
• 4 k：查找大于等于 $k$ 的数字中，位置最小为多少。

上述查询如果没有找到符合条件的位置则输出-1。

输入格式

第一行，两个的整数，分别是 $n$ 和 $q$ 。

第二行，$n$ 个整数，$a_1,a_2,a_3,a_4,a_5……a_n$

接下来 $q$ 行，每行两个整数，分别是查询方案 $op$ 和 $k$

输出格式

共 $q$ 行，每行一个整数代表符合条件数字所在的下标。

样例数据

5 6
3 8 8 10 13
1 8
2 8
3 8
4 8
2 1
3 13

1
3
4
2
-1
-1

数据范围

对于$100\%$数据，$1 \leq n,q \leq 10^6$ ，$1 \leq a_i,k \leq 10^9$