配点: 100 点
問題文
JOI 高中生 Aoi 喜欢思考数字序列,其中相邻项之间的差的绝对值按顺序排列。
一开始,长度是写在黑板上的。 N 序列 给出了 A_1,A_2,\ldots,A_N 上写着。
Aoi 执行以下操作。 重复 N-1 次。
- 黑板上写的数列长度为 m 序列是 假设 b_1,b_2,\ldots,b_m 。 黑板上写的数字顺序 删除 b_1,b_2,\ldots,b_m 和长度 在黑板上写下 m-1 序列 给出了 |b_1-b_2|,|b_2-b_3|,\ldots,|b_{m-1}-b_m| 。然而, 表示|x| 是 它仅由 x 的绝对值。
N-1 操作完成后,将显示黑板。 1 两个值(长度 1 序列)被写入。
最初给出了黑板上写的数列的信息,所以 编写一个程序,在完成N-1 操作后查找黑板上写的值。 完成
制約
- 2 \leqq N \leqq 2\,000.
- 0 \leqq A_i \leqq 10^9.
- 所有输入值都是整数。
小課題
- (25 点) N=2.
- (75 点)没有额外的限制。
入力
输入按照以下格式给出。
N A_1 A_2 \cdots A_N
出力
N-1 运算后,输出黑板上写的值。
入力例 1
4 3 1 4 1
出力例 1
1
一开始,长度就在黑板上。 4 序列 给出了 3,1,4,1 上写着。
葵是 执行 (4-1=)3 操作。
- 1 在第二次操作中,长度为 写入 4 序列 给出了 3,1,4,1 和长度 在黑板上写下 3 序列 给出了 2,3,3 。
- 2 在第二次操作中,长度为 写入 3 序列 给出了 2,3,3 和长度 在黑板上写下 2 序列 给出了 1,0 。
- 3 在第二次操作中,长度为 写入 2 序列 给出了 1,0 和长度 在黑板上写下 1 序列 给出了 1 。
3 完成运算后黑板上写下的值为 1 ,所以1 。
此输入示例是一个小作业。 2 满足约束。
入力例 2
2 2 4
出力例 2
2
此输入示例满足所有子任务约束。
入力例 3
6 2 7 5 3 3 11
出力例 3
3
此输入示例是一个小作业。 2 满足约束。
入力例 4
10 3 1 4 1 5 9 2 6 5 3
出力例 4
0
此输入示例是一个小作业。 2 满足约束。
入力例 5
2 0 0
出力例 5
0
此输入示例满足所有子任务约束。