描述

给出N及一列N个数$A_1$,$A_2$,...,$A_N$
M次询问
每次询问给出两个参数f,p
f=1表示询问p后大于$A_p$的第一个数(最靠前)的位置
f=2表示询问p前大于$A_p$的第一个数(最靠后)的位置
f=3表示询问p前小于$A_p$的第一个数(最靠后)的位置
f=4表示询问p后小于$A_p$的第一个数(最靠前)的位置

输入

第一行两个正整数N,M
第二行N个整数
接下来M行，每行两个数f,p

输出

M行，每行一个整数为所求位置，该位置不存在则输出-1

样例

输入

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

输出

3
1
-1
1

范围

50% N<=3000 M<=3000
70% N<=50000 M<=50000
90% N<=$10^6$ M<=500000
100% N<=$7\ast 10^6$ M<=$10^6$

限制

1s
128M