Palindrome?

Myeongwoo and Hongjun play a palindrome game.

Hongjun first writes $N$ natural numbers on a board. He then asks Myeongwoo $M$ questions.

Each question is a pair of integers $S$ and $E$ ($1 \le S \le E \le N$). It asks whether the numbers from the $S$-th to the $E$-th on the board form a palindrome, and Myeongwoo must answer yes or no. A sequence is a palindrome when reading it forward gives the same result as reading it backward.

Suppose Hongjun writes 1, 2, 1, 3, 1, 2, 1 on the board.

• With $S = 1$, $E = 3$ the numbers are 1, 2, 1, which is a palindrome.
• With $S = 2$, $E = 5$ the numbers are 2, 1, 3, 1, which is not a palindrome.
• With $S = 3$, $E = 3$ the number is 1, which is a palindrome.
• With $S = 5$, $E = 7$ the numbers are 1, 2, 1, which is a palindrome.

Given the $N$ numbers and the $M$ questions, write a program that produces all of Myeongwoo's answers.

The first line contains the size of the sequence $N$ ($1 \le N \le 2000$).

The second line contains the $N$ numbers Hongjun wrote on the board, in order. Each number is a natural number no greater than 100,000.

The third line contains the number of questions $M$ ($1 \le M \le 10^6$).

Each of the next $M$ lines contains one question, given as $S$ and $E$.

Print Myeongwoo's answers on $M$ lines, in the order the questions are given. Print 1 if the range is a palindrome and 0 if it is not.