Задача №3322. k-й ноль на интервале
Реализуйте структуру данных для эффективного вычисления индекса k-го слева нулевого элемента в отрезке массива.
Входные данные
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.
Во второй строке вводятся N чисел от 0 до 100000 — элементы массива.
В третьей строке вводится одно натуральное число M (1 ≤ M ≤ 30000) — количество запросов на вычисление количества нулей.
В следующих M строках вводится по три числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы) и число k (1 ≤ k ≤ N).
Выходные данные
Для каждого запроса выведите индекс элемента массива, который является k-м слева нулевым элементом на соответствующем участке массива. Числа выводите в одну строку через пробел.
Примеры
Входные данные
5 0 0 2 0 1 5 1 5 2 2 4 2 3 5 3 1 1 1 3 4 1
Выходные данные
2 4 -1 1 4
Сдать: для сдачи задач необходимо войти в систему