Олимпиадный тренинг

Задача . C. Не равный на отрезке

Задача

Вам задан массив из n целых чисел a, а также m запросов. Каждый запрос задан тройкой целых чисел l_i, r_i, x_i.

Для каждого запроса вам нужно найти любую позицию p_i (l_i ≤ p_i ≤ r_i) такую, что a_{p_i} ≠ x_i.

Входные данные

В первой строке находится пара целых чисел n, m (1 ≤ n, m ≤ 2·10⁵) — количество чисел в массиве и количество запросов.

Во второй строке находятся n целых чисел a_i (1 ≤ a_i ≤ 10⁶) — элементы массива a.

В следующих m строках заданы запросы тремя целыми числами l_i, r_i, x_i (1 ≤ l_i ≤ r_i ≤ n, 1 ≤ x_i ≤ 10⁶) — параметры i-го запроса.

Выходные данные

Выведите m строк. На i-й строке выведите целое число p_i — позицию любого числа в отрезке [l_i, r_i] не равного x_i, либо число - 1, если такого числа нет.

Примеры

№	Входные данные	Выходные данные
1	6 4 1 2 1 1 3 5 1 4 1 2 6 2 3 4 1 3 4 2	2 6 -1 4

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет