题目描述

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

输入格式

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

输出格式

共一行，一个整数表示 $m$。

5
12348
53655
60080
47800
57548

115716

数据规模和约定

对于 $100\%$ 的数据，$n \le 2 \times 10^4$，$0 \le a_i \le 10^9$。

此题存在版权，故原 BZOJ 不再支持提交，保留在此只供大家参考题面！ 望见谅！