题目描述

邪恶的面条老师会给出一个从小到大排好序的数列 $a$（长度为 $n$），并进行以下四种询问：

• 1 x：查询数列中从左到右第一个大于等于 $x$ 的位置。如果找不到（数列中所有数都小于 $x$），输出 $n+1$。
• 2 x：查询数列中从左到右第一个大于 $x$ 的位置。如果找不到（数列中所有数都小于等于 $x$），输出 $n+1$。
• 3 x：查询数列中从左到右最后一个小于等于 $x$ 的位置。如果找不到（数列中所有数都大于 $x$），输出 $0$。
• 4 x：查询数列中从左到右最后一个小于 $x$ 的位置。如果找不到（数列中所有数都大于等于 $x$），输出 $0$。

输入格式

第一行读入两个整数 $n,m$，表示数列的长度为 $n$，一共有 $m$ 次询问。

第二行读入 $n$ 个整数表示数列 $a$。

接下来 $m$ 行，每行两个正整数 $p,x$，表示进行第 $p$ 种询问。

输出格式

对于每次询问输出一行一个整数表示询问的答案。

6 5
-7 -2 3 3 3 6
1 -2
2 -2
3 3
4 3
4 -9

2
3
5
2
0

提示

对于 $100 \%$ 的数据：$1\leqslant n,m \leqslant 10^{5},$ $-10^9 \leqslant a_i,x\leqslant 10^9$。

提示：你可以通过测试点的通过情况来判断是哪一种询问写错了。