ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2008

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

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

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

Исходные данные

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

Результат

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

Пример

исходные данныерезультат
5
1234567 666666 3141593 666666 4343434
5
1 5 3141593
1 5 578202
2 4 666666
4 4 7135610
1 1 1234567
10101
Автор задачи: Александр Ипатов
Источник задачи: XII чемпионат Урала по спортивному программированию, 29 марта 2008 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1613. Для любителей статистики