import sys
read = lambda : sys.stdin.readline().strip()
write = lambda x: sys.stdout.write(str(x)+ "\n")

sys.setrecursionlimit(10**8)
d = [[-1 for i in range(2001)] for j in range(2001)]
# d[i+1][j-1]
# i+1부터 j-1까지 펠린드롭인지 아닌지 확인하는 것
def fel (x, y):
    if x == y:
        return 1
        # 길이가 1일 때
    elif x+1 == y:
        # 글자가 2일 때
        if a[x] == a[y]:
            return 1
        else:
            return 0

    if d[x][y] != -1:
        return d[x][y]
        # memoization

    if a[x] != a[y]:
      # x와 y가 같지않으면 바로 0준다.
        d[x][y] = 0
        return d[x][y]
    else:
      # 같다면 이제 그속의 다른 애들도 같나 확인을 하기 위해 recursive돈다
        d[x][y] = fel(x+1, y-1)
        return d[x][y]


read()
a = read().split()
for i in range(int(read())):
  ap, dui = map(int, read().split())
  if fel(ap-1, dui-1) == False:
      write(0)
  else:
      write(1)

import sys
read = lambda : sys.stdin.readline().strip()
write = lambda x: sys.stdout.write(str(x)+ "\n")

d = [[False for _ in range(2001)] for _ in range(2001)]
# d[i+1][j-1]
# i+1부터 j-1까지 펠린드롭인지 아닌지 확인하는 것
n = int(read())
a = read().split()

for i in range(n):
    d[i][i] = True

for j in range(n-1):
    if a[j] == a[j+1]:
        d[j][j+1] = True

for k in range(2, n):
    for i in range(0, n-k):
        j = i + k
        if (a[i] == a[j]) and d[i+1][j-1]:
            d[i][j] = True

for _ in range(int(read())):
    s, e = map(int, read().split())
    if d[s-1][e-1]:
        write(1)
    else:
        write(0)

import sys
read = lambda : sys.stdin.readline().strip()
write = lambda x: sys.stdout.write(str(x)+ "\n")

sys.setrecursionlimit(10**8)
save = [[-1 for i in range(2001)] for j in range(2001)]

def fel (a,b):
    if save[a][b] != -1:
        return save[a][b]
    elif a >= b:
        return 1
    elif seq[a] != seq[b]:
        save[a][b] = 0
        return 0
    else:
        save[a][b] = fel(a+1, b-1)
        return save[a][b]

read()
seq = read().split()
for i in range(int(read())):
  ap, dui = map(int, read().split())
  write(fel(ap-1, dui-1))