题目描述

$n$ 只猴子围成一圈，依次编号为 $1$ ~ $n$。$1$ 号和 $2$ 号相邻，$2$ 号和 $3$ 号相邻，……，$n-1$ 号和 $n$ 号相邻，$n$ 号和 $1$ 号相邻。

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

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

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

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

输入格式

第一行：一个整数 $n$。

接下来 $n$ 行，每行一个整数 $x_i$。

输出格式

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

样例输入

4
1
1
2
2

样例输出

4

数据范围

共 $20$ 个测试点，全部满足：$1 ≤ n ≤ 20,000$，$1 ≤ x_i ≤ 10^5$。

其中：

有 $5$ 个测试点：$1 ≤ n ≤ 10$

有 $5$ 个测试点：$10 < n ≤ 1,000$

有 $10$ 个测试点：$1000 < n ≤ 20,000$