时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
Cubercsl 喜欢吃序列，所以这一天不知道谁送了他一个序列，他非常快乐，想把他吃完。
序列的每一段自然也有好吃与不好吃的分别，他用数字标识了每个部分的美味度（可能是负的）。
现在，他可以从头或从尾部花费 1 秒吃掉这个序列的一个元素，并获得这个元素此时的美味度。但是，令他头疼的是，每经过 1秒，所有还没有被吃的部分的美味度会下降 1。
现在 Cubercsl 想知道，如果他按照合理的顺序吃完这个序列，他能获得的最大的美味度的和是多少？
序列的每一段自然也有好吃与不好吃的分别，他用数字标识了每个部分的美味度（可能是负的）。
现在，他可以从头或从尾部花费 1 秒吃掉这个序列的一个元素，并获得这个元素此时的美味度。但是，令他头疼的是，每经过 1秒，所有还没有被吃的部分的美味度会下降 1。
现在 Cubercsl 想知道，如果他按照合理的顺序吃完这个序列，他能获得的最大的美味度的和是多少？
输入描述:
第一行包含一个整数 n () ，表示序列的长度。
第二行包含 n 个整数(
)，中间以空格分隔，分别表示这个序列每一部分的美味度。
输出描述:
在一行输出一个整数，表示吃完这个序列能获得的最大美味度的和。