Palindrome?

Interview

Time limit0.5sMemory limit256 MB

Summary

Answer up to a million queries asking whether a given range of the number sequence is a palindrome.

Level: Medium4 of 10
Topics: Dynamic programming, Intervals
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

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.

Examples6

Example 1

Input

7
1 2 1 3 1 2 1
4
1 3
2 5
3 3
5 7

Expected output

Example 2
Input
```
1
1
1
1 1
```
Expected output
```
1
```

Example 3

Input

Expected output

Example 4

Input

6
1 2 3 4 5 6
7
1 6
1 2
2 3
3 3
4 6
5 6
1 1

Expected output

Example 5

Input

8
1 2 2 1 3 3 1 1
8
1 4
2 3
5 6
7 8
1 8
4 5
3 6
2 7

Expected output

Example 6

Input

5
100000 99999 100000 99999 100000
5
1 5
1 3
2 4
1 2
3 5

Expected output