#PQJ2767x15271. QOJ 2767_15271
QOJ 2767_15271
第四题 皇帝的烦恼(文件名:trouble)
时限:1s 分值:100
试题描述 经过多年的杀戮,秦皇终于统一了中国。为了抵御外来的侵略,他准备在国 土边境安置n 名将军。 不幸的是这n 名将军羽翼渐丰,开始展露他们的狼子野心了。他们拒绝述职、 拒绝接受皇帝的圣旨。秦皇已经准备好了秘密处决这些无礼的边防大将。不过为 防兵变,他决定先授予这些将军一些勋章,为自己赢得战略时间。 将军们听说他们即将被授予勋章都很开心,他们纷纷上书表示感谢。第i 个 将军要求得到ai 枚不同颜色的勋章。但是这些将军都很傲气,如果两个相邻的将 军拥有颜色相同的勋章他们就会认为皇帝不尊重他们,会立即造反(编号为i 的 将军和编号为i+1 的将军相邻;因为他们驻扎的边境可以类似看成一个圆形,所 以编号1 和编号n 的将军也相邻)。 皇帝不得不满足每个将军的要求,但对他们的飞扬跋扈感到很气愤。于是皇 帝决定铸造尽量少种类的勋章来满足这些狂妄者的要求。请问他至少要铸造多少 种颜色的勋章?
输入 输入文件第一行有一个整数n(1<=n<=20000)。 接下来n 行每行一个整数ai,表示第i 个将军要求得到多少种勋章。 (1<=ai<=100000)
输出 输出一个整数,即最少需要多少种勋章。
样例 trouble.in 4 2 2 1 1 trouble.out 4