#8194. 「蓝桥杯202403C1」靶场 暂未评定

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

靶场上有n块靶排成一排,从左到右依次编号为 ,且每块靶上都标有一个整数。当某块靶被击中后,击中者会得到 的积分。( 表示被击中的靶上的数, 表示其左侧最近且未被击中的靶上的数, 表示其右侧最近且未被击中的靶上的数。如果其左侧不存在未被击中的靶,则 ;如果其右侧不存在未被击中的靶,则 。)计算完积分 后,这块靶就会退出靶场(不在这排靶中)。请计算击中所有靶后能得到的最高积分是多少?

例如:,表示有 块靶,这4块靶上的数从左到右分别是 ; 按照下列顺序打靶,可以得到最高积分:

  1. 号靶,得到的积分是 );
  2. 号靶,得到的积分是 );
  3. 号靶,得到的积分是 );
  4. 号靶,得到的积分是 );

最终获得的积分是 )。

输入格式

第一行输入一个整数 ),表示靶场上靶的数量。 第二行输入 个整数(),分别表示从左到右每块靶上的数,整数之间以一个空格隔开

输出格式

输出一个整数,表示击中所有靶后能得到的最高积分。

样例

样例输入

4
3 2 4 6

样例输出

120