#55. 猴子与小球

猴子与小球

题目描述

nn 只猴子围成一圈,依次编号为 11 ~ nn。11 号和 22 号相邻,22 号和 33 号相邻,……,n−1n-1 号和 nn 号相邻,nn 号和 11 号相邻。

现在要给它们分发一些不同颜色的小球。

编号为 ii 的猴子希望得到 xix_i 个颜色互不相同的小球。

如果两只相邻的猴子被分到相同颜色的小球,它们就会发生争抢,希望自己能独有那种颜色的小球。

为了让所有猴子都不会发生争抢,至少需要准备多少种颜色的小球?

输入格式

第一行:一个整数 nn。

接下来 nn 行,每行一个整数 xix_i。

输出格式

一个整数,表示最少需要准备的颜色种数。

样例输入

4
1
1
2
2

样例输出

4

数据范围

共 2020 个测试点,全部满足:1≤n≤20,0001 ≤ n ≤ 20,000,1≤xi≤1051 ≤ x_i ≤ 10^5。

其中:

有 55 个测试点:1≤n≤101 ≤ n ≤ 10

有 55 个测试点:10<n≤1,00010 < n ≤ 1,000

有 1010 个测试点:1000<n≤20,0001000 < n ≤ 20,000