돌 가져가기 게임

정후와 동현이는 오래된 앙숙이다. 오늘은 누가 정보올림피아드를 더 잘하는지를 두고 논쟁이 붙었다. 동현이는 우열을 가리기 위해 정후에게 게임을 제안했다.

1. N개의 정점이 원형으로 배치된 사이클 모양의 경기장이 있다.
2. 사이클의 각 간선에는 돌들이 놓여 있다.
3. 시작점에 말을 놓고 동현이부터 번갈아가며 말이 있는 정점과 인접한 간선 중 하나를 골라 말을 이동시킨다. 이때 그 간선에 놓인 돌을 하나 이상 원하는 만큼 주워야 한다. 간선에 돌이 없다면 그 방향으로 이동할 수 없다.
4. 말을 더 이상 이동할 수 없는 사람이 패배한다.

동현이가 먼저 시작하는 데 불만을 품은 정후는 게임이 시작되기 전에 돌을 미리 준비해두었다. 정후는 준비한 돌을 원하는 간선에 추가할 수 있다. 가져온 돌을 꼭 하나의 간선에 모두 넣을 필요는 없다. 경기장의 상태에 따라 시작점의 위치가 중요해진다. 시작점이 어디이든 정보올림피아드 국가대표인 동현이는 최선의 플레이를 한다. 정후는 가져올 돌의 개수를 정확히 계산하려 한다. 정후가 이기는 시작점이 각각 적어도 $i$개 ($1 \le i \le N$) 이상이 되도록 정후가 가져와야 하는 돌의 최소 개수를 구하라.

첫 번째 줄에 정수 $N$이 주어진다. 두 번째 줄에는 $i$번 정점과 $(i+1) \bmod N$번 정점을 잇는 간선에 놓인 돌의 개수 $A_i$가 시계방향으로 $N$개 주어진다.

$i$번째 줄에 정후가 이기는 시작점이 적어도 $i$개가 되도록 하는 돌의 최소 개수를 출력한다. 그런 개수를 만들 수 없다면 -1을 출력한다.

$1 \le N \le 400$ $1 \le A_i \le 1{,}000{,}000{,}000$