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