G-Birusu的公园_第五届武汉纺织大学ACM程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Hakaishin星有一个圆形公园，公园的外围长有一些树（公园的外围可以表示成一个 $n$ 个节点的环，每个节点 $v_i$ 上有一棵树，其高度为 $h_i$ ），如图。

Birusu准备在公园的外围上建一条圆弧形的小道，小道有一个入口 $s$ 和一个出口 $t$ （入口 $s$ 和出口 $t$ 不能在同一个节点上,所以小道长度至少为 $2$ ) 并且除了入口 $s$ 和出口 $t$ 上的树，小道上其他的树高度要修剪为 ${{h_i}^{'}}=1$ 。
为了美观，Birusu想要圆弧形小道上的树高度总和（包括入口 $s$ 和出口 $t$ 上的树）最大。请问小道上树高度总和最大是多少？

输入描述:

第一行输入一个整数 （）代表环上节点个数。
第二行输入  个整数 （，）代表节点  上树的高度 。

输出描述:

一个整数，代表小道上树高度的最大总和。

示例1

输入

复制

5
5 9 5 9 5

输出

复制

说明

入口  为  ，出口  为  ，途径  ，，，  。
小道上树高度总和为 。