승현이는 정점의 개수가 N개인 방향성 그래프 G와 음이 아닌 정수들로 구성된 배열 A[1],A[2],⋯,A[N−1]을 가지고 있습니다. 정점들에는 0 이상 N−1 이하의 정수 번호가 붙어 있으며, 각 간선에는 가중치가 존재합니다. 초기에 이 방향성 그래프에는 간선이 하나도 없었기 때문에, 승현이는 허전함을 느꼈습니다. 이에 그는 아래와 같은 방식으로 간선들을 잇기로 했습니다.</p>

• 임의의 두 정점 u와 v (0≤u,v<N,u≠v)에 대하여,
  • 만약 u>v이고 A[u−v]의 값이 양수라면, u에서 v로 향하는 가중치가 A[u−v]인 간선을 추가합니다.
  • 만약 u<v이고 A[u−v+N]의 값이 양수라면, u에서 v로 향하는 가중치가 A[u−v+N]인 간선을 추가합니다.
  </li> </ul>

  승현이는 이렇게 간선을 추가한 뒤에 임의의 정점에서 출발하여 다른 정점에 도착하는 최단 경로의 길이를 구하고자 합니다.

  입력 형식

  첫 번째 줄에 그래프 G의 정점의 수 N (5≤N≤2,000)이 주어집니다. 두 번째 줄에 A[1],A[2],⋯,A[N−1] (0≤A[1],A[2],⋯,A[N−1]≤10,000)이 공백을 사이로 두고 주어집니다. 세 번째 줄에 질의의 수 Q (1≤Q≤200,000)가 주어집니다. 이후 Q개 줄이 주어지는데, 이 중 i번째 줄 (1≤i≤Q)에는 두 개의 정수 a_i와 b_i (0≤a_i,b_i<N, a_i≠b_i)가 공백을 사이로 두고 주어집니다.

  출력 형식

  여러분은 각 질의마다 a_i번 정점에서 출발하여 b_i번 정점에 도착하는 최단 경로의 길이를 한 줄에 하나씩 입력에서 주어진 순서대로 출력해야 합니다. 단 이러한 최단 경로가 존재하지 않을 경우 −1을 출력합니다.

  예제 입력 1

  5
  3 2 0 0
  4
  1 0
  2 1
  3 0
  0 1

  예제 출력 1

  3
  3
  5
  4

  예제 입력 2

  6
  0 3 0 0 0
  4
  0 4
  1 2
  2 3
  4 0

  예제 출력 2

  3
  -1
  -1
  6