구출 작전

CLRS(Criminal Liberating Rough Squad)는 사막을 가로질러 다른 감옥으로 죄수들을 이송하는 열차를 습격해 죄수 일부라도 풀어주려 한다.

CLRS는 트럭을 정확히 10대 확보했고, 이 트럭으로 구출한 죄수들을 습격 현장에서 임시 비행장까지 운반한다. 비행장에서는 죄수들을 태우고 해외로 떠날 비행기들에 연료를 채우고 있다.

습격 현장에서 CLRS는 열차 한 칸에 침입해 경비를 제압하고, 그 칸의 죄수 전원을 풀어준 뒤 다음 칸으로 이동한다. 이들은 처음 습격한 칸에서 열차 끝을 향해 한 칸씩 나아가며 죄수들을 차례로 구출한다. CLRS는 습격한 칸의 죄수 전원을 반드시 풀어 트럭에 태운다고 자부한다. CLRS는 열차 안에서 한 방향으로만 움직이며 결코 되돌아가지 않는다.

다소 이상하지만, 트럭이 현장을 떠날 때 모든 트럭에 탄 구출된 죄수의 수가 정확히 같아야 한다. 이는 CLRS의 오랜 안전 미신이며, 이런 작전에서는 어떤 대가를 치르더라도 깨뜨릴 수 없다.

나쁜 소식도 있다. 경찰이 비교적 가까운 곳에서 순찰할 가능성이 높으므로, 최초 습격 후 가능한 한 빨리 현장을 떠나야 한다. 즉, 미신 규칙이 허락하는 즉시 떠나야 한다.

작전이 불가능한 경우도 있다. 예를 들어 CLRS가 열차 끝에 너무 가까운 칸에서 습격을 시작하는 경우다.

이제 모든 것을 신중히 계획해야 한다. 각 칸에 실린 죄수의 수는 CLRS가 미리 알고 있다. 이들은 열차의 각 칸마다, 그 칸에서 습격을 시작하면 몇 개의 칸을 습격해야 하는지 알고 싶어 한다.

첫째 줄에 열차의 칸 수 N (1 ≤ N ≤ 105)이 주어진다. 둘째 줄에 각 칸에 실린 죄수의 수를 나타내는 0 이상 9 이하의 값 N개가 주어진다. 값은 열차의 첫 칸부터 마지막 칸 순서로 나열된다.

출력은 N개의 수로 이루어진 수열이다. 수열의 k번째 값은 k번째 칸에서 습격을 시작할 때 습격하는 칸의 수이다. k번째 칸에서 시작해 작전을 완수할 수 없다면 그 값은 −1이다.