자연수 \(N\)개가 적힌 수열이 있다. 이 수열에 대해 \(M\)개의 질문이 주어진다.

각 질문은 두 정수 \(S\)와 \(E\)로 이루어진다. 질문마다 수열의 \(S\)번째 수부터 \(E\)번째 수까지를 순서대로 나열했을 때, 앞에서 읽은 결과와 뒤에서 읽은 결과가 같은지 판별해야 한다.

예를 들어 수열이 \(1, 2, 1, 3, 1, 2, 1\)이라면 다음과 같다.

• \(S=1, E=3\)인 구간 \(1, 2, 1\)은 팰린드롬이다.
• \(S=2, E=5\)인 구간 \(2, 1, 3, 1\)은 팰린드롬이 아니다.
• 원소가 하나뿐인 구간은 항상 팰린드롬이다.

각 질문에 대한 답을 구하여라.

입력

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

둘째 줄에 수열을 이루는 자연수 \(N\)개가 공백으로 구분되어 주어진다. 각 수는 \(100,000\) 이하이다.

셋째 줄에 질문의 개수 \(M\)이 주어진다.

다음 \(M\)개의 줄에 두 정수 \(S\)와 \(E\)가 공백으로 구분되어 주어진다.

• \(1 \le N \le 2,000\)
• \(1 \le M \le 1,000,000\)
• \(1 \le S \le E \le N\)

출력

각 질문에 대해 해당 구간이 팰린드롬이면 1, 아니면 0을 한 줄에 하나씩 출력한다.

예제 입력 1

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

예제 출력 1

1
0
1
1