题目背景

在莆田的传统习俗中，正月初二是不能走亲戚拜年的。

于是小T决定在初二这天组织同学玩一个游戏。

题目描述

游戏规则如下：一共有 $N$ 人参加小T的游戏，$N$ 个人围成一圈，他们的编号分别为：$1$ 号到 $N$ 号。

$1$ 号同学分别和 $2$ 号以及 $N$ 号同学相邻。

然后第 $i$ 个同学会告诉小T一个自己的幸运数字 $a_i$ ，小T需要给第 $i$ 个同学 $a_i$ 颗颜色不同的珠子，且需要确保任意相邻的两人所拥有的珠子颜色不能重复。

由于小T的囊中羞涩，希望用尽可能少的珠子来完成这个游戏，请你用编程告诉他最少需要准备多少颗珠子。

输入格式

第一行有一个整数 $N$ 。

第二行包含 $N$ 个整数依次表示编号为 $i$ 的人需要分配的珠子数，两数间用一个空格分隔。

输出格式

一个数，表示珠子不同颜色的最少种类。

样例数据

输入样例#1

4
2 2 1 1

输出样例#1

4

样例1解释： 假设不同颜色珠子编号为：1，2，3，4……

1号同学拿：1，2

2号同学拿：3，4

3号同学拿：1

4号同学拿：3

上述方案符合相邻人珠子颜色不重复的要求，且没有珠子数量更少的方案，故答案为4

输入样例#2

5
3 1 2 3 2

输出样例#2

6

样例 2 解释： 假设不同颜色珠子编号为：1，2，3，4……

1号同学拿：1，2，3

2号同学拿：4

3号同学拿：5，6

4号同学拿：1，2，3

5号同学拿：5，6

上述方案符合相邻人珠子颜色不重复的要求，且没有珠子数量更少的方案，故答案为6

数据范围

对于$20\%$数据，$1 \leq n \leq 1000$

对于$30\%$数据，$n$ 为偶数

对于$100\%$数据，$1 \leq n \leq 2\times 10^4,1\leq a_i\leq 10^5$