Для любителів статистики#4421

Для любителів статистики

1 секунда

128 мегабайтів

Легка

Ви ніколи не задумувалися, скільки людей за рік перевозять трамваї в місті з населенням десять мільйонів, якщо кожен третій житель користується трамваєм двічі на день?

Припустимо, що на планеті Земля є $n$ міст, в яких діють трамвайні лінії. Любителі статистики підрахували для кожного з цих міст, скільки людей перевезли трамваї за останній рік. На основі цих даних була складена таблиця, в якій міста було відсортовано за алфавітом. Згодом з'ясувалося, що для статистичних задач назви міст не суттєві, тому їх просто замінили числами від $1$ до $n$ .

Пошукова система, що працює з цими даними, повинна вміти швидко відповідати на запит: чи існує серед міст з номерами від $l$ до $r$ хоча б одне, в якому трамваї за рік перевезли рівно $x$ осіб?

Вам потрібно реалізувати цей модуль системи.

Вхідні дані

У першому рядку задано одне ціле число $n (0 < n < 70000)$ n~(0 < n < 70000) — кількість міст.

У другому рядку містяться $n$ натуральних чисел — статистичні дані, де $i$ -те число позначає кількість осіб, перевезених трамваями $i$ -го міста за останній рік. Усі значення не перевищують $1 0^{9} - 1$ 10^9 - 1.

У третьому рядку задано ціле число $q (0 < q < 70000)$ q~(0 < q < 70000) — кількість запитів.

У наступних $q$ рядках описані самі запити. Кожен запит складається з трьох цілих чисел $l, r$ та $x (1 \leq l \leq r \leq n, 0 < x < 1 0^{9})$ x~(1 \le l \le r \le n, 0 < x < 10^9).

Вихідні дані

Виведіть рядок з $q$ символів. $i$ -й символ рядка має бути рівним ' $1$ ', якщо існує хоча б одне місто з номером від $l$ до $r$ , в якому трамваї перевезли рівно $x$ осіб. В іншому випадку виведіть ' $0$ '.

Приклади

Приклад 1