This page is still under construction.

Parts of this page are still being built. What you see may change.

Palindrome??

Time limit1sMemory limit256 MB

Summary
Answer up to a million queries asking whether a subarray of the given number sequence reads the same forward and backward.
Level

Medium5 of 10

Topics
String matching, Prefix sum
Solved
No attempts yet

Problem

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.

Input

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.

Output

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.

Examples6

  1. Example 1

    Input
    7
1 2 1 3 1 2 1
4
1 3
2 5
3 3
5 7
    Expected output
    1
0
1
1

  2. Example 2

    Input
    1
100000
1
1 1
    Expected output
    1

  3. Example 3

    Input
    8
5 5 5 5 5 5 5 5
5
1 8
2 7
4 5
1 1
3 8
    Expected output
    1
1
1
1
1

  4. Example 4

    Input
    7
1 2 2 1 2 2 1
7
1 4
2 3
1 7
2 6
4 7
3 6
1 2
    Expected output
    1
1
1
1
1
0
0

  5. Example 5

    Input
    10
1 2 3 4 5 6 7 8 9 10
5
1 10
1 2
5 5
9 10
3 7
    Expected output
    0
0
1
0
0

  6. Example 6

    Input
    6
100000 1 100000 100000 1 100000
6
1 3
1 6
2 5
3 4
1 4
4 6
    Expected output
    1
1
1
1
0
1