레이블
면접 대비시간 제한2초메모리 제한1024 MB
값이 1부터 N까지인 미지의 수열 A의 차분 수열 D가 주어질 때, A가 유일하게 정해지면 A를 출력하고 아니면 -1을 출력한다.
문제
택배 기사 찰스는 오늘 첫 출근이다. 찰스는 N개의 택배를 배달해야 하며, 각 택배에는 1 이상 N 이하의 레이블 번호가 붙어 있다. 이 번호는 서로 같아도 된다. 찰스는 매일 근무를 마치면 i번째로 배달한 택배의 레이블 번호를 Ai라 할 때, N개의 정수로 이루어진 수열 A1, ..., AN을 보고해야 한다.
수학을 좋아하는 찰스는 메모리 공간을 아끼려고 델타 인코딩을 쓰기로 하고, 대신 Di = Ai+1 - Ai인 N - 1개의 정수로 이루어진 수열 D1, ..., DN-1을 기록한다.
모든 택배를 배달한 뒤, 찰스는 D에서 A를 복원하는 방법을 모른다는 사실을 깨달았다. 오늘 당신의 임무는 찰스를 도와주는 것, 또는 A를 유일하게 복원하는 것이 불가능하다고 알려주는 것이다.
입력
프로그램은 표준 입력에서 입력을 읽는다.
첫째 줄에는 택배의 총 개수 N이 주어진다.
둘째 줄에는 N - 1개의 정수 D1, ..., DN-1이 공백으로 구분되어 주어진다. Di는 i+1번째로 배달한 택배와 i번째로 배달한 택배의 레이블 번호 차이를 나타낸다.
출력
프로그램은 표준 출력에 결과를 출력한다.
D에서 A를 유일하게 복원할 수 있으면, N개의 정수로 이루어진 수열 A를 공백으로 구분하여 출력한다.
그렇지 않으면 한 줄에 정수 -1 하나만 출력한다.
제한
- 2 ≤ N ≤ 3 × 105
- 1 ≤ Ai ≤ N
- -N < Di < N