28246번 - 돌 가져가기 게임

문제

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

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

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

입력

첫 번째 줄에 정수 N이 주어진다.

두 번째 줄에 경기장의 i번 정점과 (i+1) mod N번 정점을 잇는 간선에 놓인 돌의 개수를 의미하는 N개의 정수 A[i]가 시계방향으로 주어진다.

출력

i번째 줄에 정후가 이기는 시작점이 적어도 i개가 되도록 하는 돌의 최소 개수를 출력한다. 만약 정후가 이기는 시작점이 i개 이상이 되도록 하는 게 불가능하다면, -1을 출력한다.

제한

• 1 ≤ N ≤ 400
• 1 ≤ A[i] ≤ 1,000,000,000

힌트