Description

今日又在看甄嬛传，皇上觉得后宫们的勾心斗角太险恶了，有点不好，决定给每个妃子发丝带以让后宫之间和睦相处。皇上一共有N个后宫（标号为1~n），站成一个环形（1号与n号相邻），每个后宫想要ai个丝带，而且这ai个丝带颜色互不相同，而且每个妃子拥有的丝带不能与和她相邻的妃子的丝带有任何一种颜色相同。皇上不喜欢太多的颜色，所以皇上就像知道最少需要多少种颜色就能满足所有后宫的要求，设最小颜色为M，而甄嬛想提前知道M的值，以告诉皇上来赢得欢心，然而在皇上后宫太多了，她就不会了，所以呢，她向学信息奥赛的你求助，并答应事成之后奖励你

（（21,000,000,006 mod 1,000,000,007 ）-1）吨黄金

Format

Input

第一行一个整数n，接下来有n个数字，第i个数字为ai，表示编号为i的后宫想要ai条丝带。

Output

共一行，一个整数表示M。

Samples

5
12348
53655
60080
47800
57548

115716

Limitation

100%的数据：n<=20000。0<=ai<=1,000,000,000;