함의 탐험

John은 인공지능을 연구하는 연구자이다. 그는 새로운 Limitless Logic Machine의 추론 능력을 분석하려고 하며, 한 명제가 다른 명제를 함의할 때 기계가 이를 얼마나 잘 이해하는지 확인하고자 한다.

실험에는 0과 1로 이루어진 길이 $n$의 긴 배열 $a$가 쓰인다. 각 질의는 $l$, $r$의 쌍으로 주어지며, 기계는 부분 배열 $a_l \to a_{l+1} \to \cdots \to a_r$의 함의 값을 계산해야 한다. John이 기계를 검증할 수 있도록 이 질의들의 정답을 계산하라.

함의 연산자 $\to$는 다음과 같이 정의된다.

연산은 왼쪽에서 오른쪽 순서로 계산한다. 따라서 순서는 $((\dots((a_l \to a_{l+1}) \to a_{l+2}) \to \dots) \to a_r)$이다.

첫째 줄에 배열의 크기 $n$ ($2 \leq n \leq 10^5$)이 주어진다.

둘째 줄에는 배열의 원소 $a$ ($a \in \{0, 1\}$)가 $n$개 주어진다.

셋째 줄에는 질의의 개수 $q$ ($1 \leq q \leq 10^5$)가 주어진다.

이어서 $q$개의 줄에 질의를 나타내는 두 정수 $l$, $r$ ($1 \leq l < r \leq n$)이 주어진다.

각 질의에 대해 해당 함의 연산의 결과를 한 줄에 하나씩 출력한다.