经过多年的杀戮，秦皇终于统一了中国。

为了抵御外来的侵略，他准备在国土边境安置$n$名将军。不幸的是这$n$名将军羽翼渐丰，开始展露他们的狼子野心了。他们拒绝述职、拒绝接受皇帝的圣旨。秦皇已经准备好了秘密处决这些无礼的边防大将。不过为防兵变，他决定先授予这些将军一些勋章，为自己赢得战略时间。

将军们听说他们即将被授予勋章都很开心，他们纷纷上书表示感谢。第$i$个将军要求得到$a_i$枚不同颜色的勋章。但是这些将军都很傲气，如果两个相邻的将军拥有颜色相同的勋章他们就会认为皇帝不尊重他们，会立即造反（编号为$i$的将军和编号为$i+1$的将军相邻；因为他们驻扎的边境可以类似看成一个圆形，所以编号$1$和编号$n$的将军也相邻）。

皇帝不得不满足每个将军的要求，但对他们的飞扬跋扈感到很气愤。

于是皇帝决定铸造尽量少种类的勋章来满足这些狂妄者的要求。请问他至少要铸造多少种颜色的勋章？

输入格式

第一行有一个整数$n(1 \leq n \leq 20000)$。

接下来$n$行每行一个整数$a_i$，表示第$i$个将军要求得到多少种勋章。($1 \leq a_i \leq 100000$)

输出格式

输出一个整数，即最少需要多少种勋章。

样例输入

4
2
2
1
1

样例输出

4