Not Equal on a Segment

题意翻译

【题目描述】 给定一个有n个整数和m个查询的A数组。第i个查询是三个整数l[i]，r[i]，x[i]。对于第i个查询，查找任何位置p[i]（l[i]<=p[i]<=r[i]），以便a[p[i]]≠x[i]。 【输入格式】 第一行包含两个整数n和m（1<=n，m<=2乘10^5）-a中元素的数目和查询的数目。 第二行包含n，整数a[i]（1<=a[i]<=10^6）-数组a的元素。 接下来的m行中的每一行都包含三个整数，l[i]、r[i]、x[i]。（1<=l[i]<=r[i]<=n，1<=x[i]<=10^6）-第i个查询的参数。 【输出格式】 **输出为m行**。在第i行打印整数p[i]——段[l[i]，r[i]]中不等于x[i]的任何数字的位置，**如果没有该数字，输出-1。**

题目描述

You are given array $ a $ with $ n $ integers and $ m $ queries. The $ i $ -th query is given with three integers $ l_{i},r_{i},x_{i} $ . For the $ i $ -th query find any position $ p_{i} $ ( $ l_{i}<=p_{i}<=r_{i} $ ) so that $ a_{pi}≠x_{i} $ .

输入输出格式

输入格式

The first line contains two integers $ n,m $ ( $ 1<=n,m<=2·10^{5} $ ) — the number of elements in $ a $ and the number of queries. The second line contains $ n $ integers $ a_{i} $ ( $ 1<=a_{i}<=10^{6} $ ) — the elements of the array $ a $ . Each of the next $ m $ lines contains three integers $ l_{i},r_{i},x_{i} $ ( $ 1<=l_{i}<=r_{i}<=n,1<=x_{i}<=10^{6} $ ) — the parameters of the $ i $ -th query.

输出格式

Print $ m $ lines. On the $ i $ -th line print integer $ p_{i} $ — the position of any number not equal to $ x_{i} $ in segment $ [l_{i},r_{i}] $ or the value $ -1 $ if there is no such number.

输入输出样例

输入样例 #1

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

输出样例 #1

2
6
-1
4