eolymp
bolt
Try our new interface for solving problems
Məsələlər

Для любителей статистики

Для любителей статистики

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Вы никогда не задумывались над тем, сколько человек за год перевозят трамваи города с десятимиллионным населением, в котором каждый третий житель пользуется трамваем по два раза в день?

Предположим, что на планете Земля n городов, в которых есть трамваи. Любители статистики подсчитали для каждого из этих городов, сколько человек перевезено трамваями этого города за последний год. Из этих данных была составлена таблица, в которой города были отсортированы по алфавиту. Позже выяснилось, что для статистики названия городов несущественны, и тогда их просто заменили числами от 1 до n. Поисковая система, работающая с этими данными, должна уметь быстро отвечать на вопрос, есть ли среди городов с номерами от l до r такой, что за год трамваи этого города перевезли ровно x человек. Вам предстоит реализовать этот модуль системы.

Giriş verilənləri

В первой строке дано целое число n (0 < n < 70000). В следующей строке приведены статистические данные в виде списка целых чисел через пробел, i-ое число в этом списке - количество человек, перевезенных за год трамваями i-го города. Все числа в списке положительны и не превосходят 10^9 - 1. В третьей строке дано количество запросов q (0 < q < 70000). В следующих q строках перечислены запросы. Каждый запрос - это тройка целых чисел l, r и x (1lrn; 0 < x < 10^9), записанных через пробел.

Çıxış verilənləri

Выведите строку длины q, в которой i-ый символ равен "1", если ответ на i-ый запрос утвердителен, и "0" в противном случае.

Nümunə

Giriş verilənləri #1
5
123 666 314 666 434
5
1 5 314
1 5 578
2 4 666
4 4 713
1 1 123
Çıxış verilənləri #1
10101
Müəllif Александр Ипатов
Mənbə XII чемпионат Урала по спортивному программированию, 29 марта 2008 г.