242040 - 相邻数字消除

题目描述

小明有一排数字 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解释:

初始序列为 [1,5,2,8]。

第一轮:[4,3,6]。

第二轮:[1,3]。

第三轮:[2]。

因此最终答案为 2。

数据范围

  • 2\le n\le5000
  • 0\le a_i\le10^9
标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 1
通过人数 1
金币数量 3 枚
难度 基础


上一题 下一题