问题描述

在魔法王国的首都，有一家神奇的面包店。店里的面包师傅小泰发现，每种面包配方都有一个独特的"美味指数"，这个指数由配方中使用的最差原料的质量乘以所有原料的总质量决定。

最近面包店举办了"最佳配方大赛"，参赛者需要从 $n$ 种原料中选择一个连续的配方区间（不能跳过任何原料），找出能使美味指数最大的配方组合。你能帮助小泰赢得比赛吗？

给定一个长度为 $n$ 的正整数数组，每个元素代表一种原料的质量。请选出一个连续的原料区间，使得该区间的"美味指数"最大。

美味指数计算公式为：区间最小值 × 区间和

输入格式

第一行一个整数 $n$ ，表示原料种类数
第二行 $n$ 个正整数，表示每种原料的质量

输出格式

输出一个整数，表示最大的美味指数

样例输入

5
1 2 3 4 5

样例输出

36

说明

选择区间 $[3,4,5]$ ，最小值为 $3$，和为 $12$ ， $3 \times 12 = 36$

数据范围

• $1 \le n \le 10^5$
• $1 \le$ 原料质量 $\le 100$