第一行两个整数 n,m
第二行n个整数a1,a2....an 。
接下来m行，每行两个整数l,r表示一组询问。
样例1
5 3
1 1 2 3 2
1 5
2 4
3 5
样例2
6 5
1 2 1 3 2 3
4 6
1 3
2 5
2 4
1 6样例1
1
-1
2
样例2
2
2
3
-1
2
对于30%的数据，1<=n,m<=10^3；
对于70%的数据，1<=n,m<=10^5；
对于100%的数据，1<=n,m<=10^6，1<=l<=r<=n，-10^<=ai<=10^9。