Palindrome??

Myeongu and Hongjun are playing a palindrome game.

First Hongjun writes N natural numbers on the board in order. Then he asks Myeongu M questions.

Each question is a pair of integers S and E (1 ≤ S ≤ E ≤ N), and it asks whether the numbers from the S-th to the E-th form a palindrome. Myeongu has to answer yes or no for every question. A sequence is a palindrome when reading it forward gives the same result as reading it backward.

For example, suppose the numbers on the board are 1, 2, 1, 3, 1, 2, 1.

• For S = 1, E = 3 the numbers are 1, 2, 1, which is a palindrome.
• For S = 2, E = 5 the numbers are 2, 1, 3, 1, which is not a palindrome.
• For S = 3, E = 3 the number is 1, which is a palindrome.
• For 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 Myeongu's answers.

The first line contains the size of the sequence N (1 ≤ N ≤ 1,000,000).

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 ≤ M ≤ 1,000,000).

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

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