小明有一排数字 a_1,a_2,\ldots,a_n,他设计了一种有趣的数字消除游戏。
每一轮游戏中,将当前序列中所有相邻的两个数字进行计算,计算结果为这两个数字的绝对差。
也就是说,如果当前序列为 a_1,a_2,\ldots,a_n,那么经过一轮操作后,新的序列变为:
|a_1-a_2|,\ |a_2-a_3|,\ldots,|a_{n-1}-a_n|
注意,所有新的数字都必须根据上一轮的原始序列计算,不能在同一轮中提前使用已经计算出来的新数字。
每经过一轮,序列长度就会减少 1。当序列只剩下一个数字时,游戏结束。
请你计算最终剩下的数字是多少。
第一行输入一个正整数 n,表示初始序列的长度。
第二行输入 n 个非负整数 a_1,a_2,\ldots,a_n。
输出一个整数,表示经过多轮操作后最终剩下的数字。
4 1 5 2 8
2
5 7 7 7 7 7
0
3 10 3 8
2
初始序列为 [1,5,2,8]。
第一轮:[4,3,6]。
第二轮:[1,3]。
第三轮:[2]。
因此最终答案为 2。