[DP] BOJ 10942 펠린드롬?

import sys
input = sys.stdin.readline
 
N = int(input()) + 1
arr = [0] + list(map(int, input().split()))
M = int(input())
dp = [[0] * N for _ in range(N)]
 
# dp table initialization 
for i in range(N):
    dp[i][i] = 1
for i in range(N-1):
    if arr[i] == arr[i + 1]: dp[i][i + 1] = 1
    
for interval in range(2, N): # 간격 설정
    for start in range(N-interval):  # 시작점
        end = start + interval # 종료점
        if arr[start] == arr[end] and dp[start + 1][end - 1] == 1:
            dp[start][end] = 1
            
 
questions = [list(map(int, input().split())) for _ in range(M)]
for start, end in questions:
    print(dp[start][end])