시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 32 MB 7 7 7 100.000%

문제

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

  • 임의의 두 정점 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]인 간선을 추가합니다.

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

입력

첫 번째 줄에 그래프 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)에는 두 개의 정수 ai와 bi (0≤ai,bi<N, ai≠bi)가 공백을 사이로 두고 주어집니다.

출력

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

예제 입력

5
3 2 0 0
4
1 0
2 1
3 0
0 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

힌트