ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. For Fans of Statistics

Time limit: 1.0 second
Memory limit: 64 MB
Have you ever thought about how many people are transported by trams every year in a city with a ten-million population where one in three citizens uses tram twice a day?
Assume that there are n cities with trams on the planet Earth. Statisticians counted for each of them the number of people transported by trams during last year. They compiled a table, in which cities were sorted alphabetically. Since city names were inessential for statistics, they were later replaced by numbers from 1 to n. A search engine that works with these data must be able to answer quickly a query of the following type: is there among the cities with numbers from l to r such that the trams of this city transported exactly x people during last year. You must implement this module of the system.

Input

The first line contains the integer n (1 ≤ n ≤ 69999). The second line contains statistic data in the form of a list of integers separated with a space. In this list, the ith number is the number of people transported by trams of the ith city during last year. All numbers in the list are positive and do not exceed 109 − 1. The third line contains an integer q that is the number of queries (1 ≤ q ≤ 69999). The next q lines contain the queries. Each of them is a triple of integers l, r, and x separated with a space (1 ≤ lrn; 1 ≤ x ≤ 109 − 1).

Output

Output a string of length q in which the ith symbol is “1” if the answer to the ith query is affirmative, and “0” otherwise.

Sample

inputoutput
5
1234567 666666 3141593 666666 4343434
5
1 5 3141593
1 5 578202
2 4 666666
4 4 7135610
1 1 1234567
10101
Problem Author: Alexander Ipatov
Problem Source: The 12th Urals Collegiate Programing Championship, March 29, 2008
To submit the solution for this problem go to the Problem set: 1613. For Fans of Statistics