A10226 | $Not Equal on a Segment$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

C++ 编辑器

输入

输出