# CF1141C Polycarp Restores Permutation

• 36通过
• 78提交
• 题目来源
• 评测方式 RemoteJudge
• 标签
• 难度 普及+/提高
• 时空限制 2000ms / 256MB
• 提示：收藏到任务计划后，可在首页查看。

## 题意翻译

有一个长度为 $n (2 \le n \le 2 \cdot 10^{5})$ 的序列 $p$ ，现在给出一个长度为 $n-1$ 的序列 $q$ ，其中 $q_{i}=p_{i+1}-p_{i}$ ，询问序列 $p$ 是否有可能是 $1 \sim n$ 的一个排列，如果可行，输出这个排列，否则输出 $-1$

## 题目描述

An array of integers $p_1, p_2, \dots, p_n$ is called a permutation if it contains each number from $1$ to $n$ exactly once. For example, the following arrays are permutations: $[3, 1, 2]$ , $[1]$ , $[1, 2, 3, 4, 5]$ and $[4, 3, 1, 2]$ . The following arrays are not permutations: $[2]$ , $[1, 1]$ , $[2, 3, 4]$ .

Polycarp invented a really cool permutation $p_1, p_2, \dots, p_n$ of length $n$ . It is very disappointing, but he forgot this permutation. He only remembers the array $q_1, q_2, \dots, q_{n-1}$ of length $n-1$ , where $q_i=p_{i+1}-p_i$ .

Given $n$ and $q=q_1, q_2, \dots, q_{n-1}$ , help Polycarp restore the invented permutation.

## 输入输出格式

输入格式：

The first line contains the integer $n$ ( $2 \le n \le 2\cdot10^5$ ) — the length of the permutation to restore. The second line contains $n-1$ integers $q_1, q_2, \dots, q_{n-1}$ ( $-n < q_i < n$ ).

输出格式：

Print the integer -1 if there is no such permutation of length $n$ which corresponds to the given array $q$ . Otherwise, if it exists, print $p_1, p_2, \dots, p_n$ . Print any such permutation if there are many of them.

## 输入输出样例

输入样例#1： 复制
3
-2 1

输出样例#1： 复制
3 1 2
输入样例#2： 复制
5
1 1 1 1

输出样例#2： 复制
1 2 3 4 5
输入样例#3： 复制
4
-1 2 2

输出样例#3： 复制
-1

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。