环链

题目描述:

在 wzms 的机房里，有着一群大大佬，大大佬们为了交流方便，就将自己的座位连成了一个环。这样就方便小蒟蒻LSH去帮他们查错了，对于帮每一个人查错都要耗费小蒟蒻 LSH T_i 的时间，然后当一个人的错误被查出时，那么他两边的人就会因为面子的关系而不向小蒟蒻 LSH 请求帮忙(当然小蒟蒻LSH 也不能主动要帮他们)，即选取 T_i 的条件就是 T_i-1 和 T_i+1 都没有被选( 当选取 T₁ 时必须是 T₂ 和 T_n 都没有被选 )。由于小蒟蒻LSH 是一个热心的人，所以他希望他的查错时间尽可能的长，请你输出他最大的查错时间。

输入格式:

第一行，一个正整数 n ( 1 ≤ n ≤ 10⁵ )，表示这个环里共有n个人。
第二行，n个正整数，即 T_i (1 ≤ T_i ≤ 10⁸)

输出格式:

一行，即LSH的最大查错时间。

样例输入:

6
10 3 2 5 7 8

样例输出:

19

时间限制: 1000ms
空间限制: 256MB

---

来源: 原创