Photoshoot¶
Farmer John 在给他编号为 1\ldots N 的 N 头奶牛排队拍照(2\le N\le 10^3)。FJ 一开始计划从左向右数第 i 个位置排编号为 a_i 的奶牛,他在一张纸上写下了排列 a_1,a_2,\ldots,a_N。不幸的是,这张纸刚刚被 Farmer Nhoj 偷走了!
幸好 FJ 仍然有机会恢复他之前写下的排列。在这张纸被偷走之前,Bessie 记录了序列 b_1,b_2,\ldots,b_{N-1},对于每一个 1\le i<N 满足 b_i=a_i+a_{i+1}。
基于 Bessie 的信息,帮助 FJ 恢复可以产生序列 b 的“字典序最小”的排列 a。排列 x 字典序小于排列 y,如果对于某个 j,对于所有 i<j 均有 x_i=y_i,且有 x_j<y_j(换句话说,这两个排列到某个位置之前都相同,在这个位置上 x 小于 y)。保证存在至少一个满足条件的 a。
测试点性质:¶
- 测试点 2-4 满足 N\le 8。
- 测试点 5-10 没有额外限制。
输入格式(文件名:photo.in):¶
输入的第一行包含一个整数 N。
第二行包含 N-1 个空格分隔的整数 b_1,b_2,\ldots,b_{N-1}。
输出格式(文件名:photo.out):¶
输出一行,包含 N 个空格分隔的整数 a_1,a_2,\ldots,a_{N}。
输入样例:¶
1 2 | 5
4 6 7 6
|
输出样例:¶
1 | 3 1 5 2 4
|
a 能够产生 b,因为 3+1=4,1+5=6,5+2=7,2+4=6。