红色警戒之CZ的复仇

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 

在上一集的故事中,CZ大战QC。不幸的是CZ最终败下阵来。就当CZ气馁将要放弃的时候CZ在沙漠中捡到了一个旺仔牛奶罐子,CZ拿起旺仔牛奶说起了那句熟悉的广告词“再看我就把你喝掉!”于是乎,他的女神凤姐突然冒了出来,女神说我可以满足你三个愿望,CZ复仇之心突起,说第一,我要一个世界上最好的一个科学家为我卖命,第二,我要一个青春靓丽的学妹。第三,把我带到我的家里去。两年后,CZ和他的科学家以及当初青春靓丽的学妹凤姐。。。终于再他的家中研制出了一种新型地道导弹——“渣斯尼”,同时CZ得到消息,QZ此时已是亿万富翁,专做军火生意,在他居住的城堡的地下有N个仓库,相邻的仓库之间有通道所有通道距离相等(例如2与1,3,相邻)。然而各个通道的质量却不一样,他允许导弹通过的次数会有所不同,当到达质量所允许的通过次数之后通道将会坍塌。而这种“渣斯尼”导弹跑的距离越长,他的威力越大。现在已知各个通道(1~n-1)允许导弹通过的次数,聪明的你,能知道导弹的最大威力(通过某通道一次导弹威力加1)么?

Input

 

输入一个数n (2 ≤ n ≤ 1e5) ,然后再输入a[i]代表各个通道的质量极限(1通道连接1号仓库和2号仓库)(1<=i< n,0<=a[i] <= 1e9)

 

 

Output

 

输出导弹的最大威力

Sample Input

5
2 1 2 1

Sample Output

5

Hint

 

Source

zyj