팰린드롬??

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

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

각 질문은 두 정수 S와 E (1 ≤ S ≤ E ≤ 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 ≤ N ≤ 1,000,000)이 주어진다.

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

셋째 줄에 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

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

M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력에 주어진 순서대로 출력한다. 팰린드롬인 경우에는 1을, 아닌 경우에는 0을 출력한다.