Intelligence Exploration

John is a researcher in artificial intelligence. He wants to analyze the reasoning ability of a new Limitless Logic Machine and check how well it understands when one statement implies another.

The experiment uses a long array $a$ of length $n$ consisting of zeroes and ones. Each query is given as a pair $l$, $r$, and the machine must compute the value of the implication over the subarray $a_l \to a_{l+1} \to \cdots \to a_r$. You must compute the correct answers to these queries so that John can validate the machine.

The implication operator $\to$ is defined as follows.

The operations are evaluated from left to right, so the order is $((\dots((a_l \to a_{l+1}) \to a_{l+2}) \to \dots) \to a_r)$.

The first line contains an integer $n$ ($2 \leq n \leq 10^5$), the size of the array.

The second line contains $n$ integers $a$ ($a \in \{0, 1\}$), the values in the array.

The third line contains an integer $q$ ($1 \leq q \leq 10^5$), the number of queries.

Each of the next $q$ lines contains two integers $l$ and $r$ ($1 \leq l < r \leq n$), describing a query.

For each query, print the result of the corresponding implication on its own line.