팰린드롬?

명우와 홍준이가 팰린드롬 놀이를 한다.

먼저 홍준이가 자연수 $N$개를 칠판에 적는다. 그 다음 명우에게 질문을 $M$번 한다.

각 질문은 두 정수 $S$와 $E$ ($1 \le S \le E \le N$)로 이루어진다. 칠판에 적힌 수 중 $S$번째 수부터 $E$번째 수까지가 팰린드롬을 이루는지 묻는 질문이고, 명우는 팰린드롬이다 또는 아니다로 답해야 한다. 수열이 팰린드롬이라는 말은 앞에서 읽은 순서와 뒤에서 읽은 순서가 같다는 뜻이다.

홍준이가 칠판에 1, 2, 1, 3, 1, 2, 1을 적었다고 하자.

• $S = 1$, $E = 3$이면 1, 2, 1이므로 팰린드롬이다.
• $S = 2$, $E = 5$이면 2, 1, 3, 1이므로 팰린드롬이 아니다.
• $S = 3$, $E = 3$이면 1이므로 팰린드롬이다.
• $S = 5$, $E = 7$이면 1, 2, 1이므로 팰린드롬이다.

자연수 $N$개와 질문 $M$개가 주어졌을 때 명우의 대답을 모두 구하는 프로그램을 작성하시오.

첫째 줄에 수열의 크기 $N$ ($1 \le N \le 2000$)이 주어진다.

둘째 줄에 홍준이가 칠판에 적은 수 $N$개가 순서대로 주어진다. 각 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에 질문의 개수 $M$ ($1 \le M \le 10^6$)이 주어진다.

넷째 줄부터 $M$개의 줄에 질문의 $S$와 $E$가 한 줄에 하나씩 주어진다.

$M$개의 줄에 걸쳐 명우의 답을 질문이 주어진 순서대로 출력한다. 팰린드롬이면 1을, 아니면 0을 출력한다.