皇帝的烦恼(Emperors Trouble)

题目描述

经过多年的杀戮，秦皇终于统一了中国。为了抵御外来的侵略，他准备在国土边境安置 $n$ 名将军。

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

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

皇帝不得不满足每个将军的要求，但对他们的飞扬跋扈感到很气愤。于是皇帝决定铸造尽量少种类的勋章来满足这些狂妄者的要求。请问他至少要铸造多少种颜色的勋章？

输入格式

第一行一个整数 $n$。

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

输出格式

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

样例输入 #1

4
2
2
1
1

样例输出 #1

4

数据范围

$1 \leq n \leq 2 \times 10^4$，$1 \leq a_i \leq 10^5$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1800。

测试点分布

出处：原题链接