题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$。

我们定义 $mi(l, r)$ 表示下标区间 $[l, r]$ 范围内所有元素的最小值，即 $mi(l, r) = \min(a_l, a_{l+1}, \ldots, a_r)$；

定义 $sum(l, r)$ 表示下标区间 $[l, r]$ 范围内所有元素之和，即 $sum(l, r) = \sum\limits_{i=l}^r a_i = a_l + a_{l+1} + \ldots + a_r$。

求：对于所有 $1 \le l \le r \le n$，$mi(l, r) \times sum(l, r)$ 的最大值。

输入格式

第一行，一个整数 $n(1 \le n \le 10^5)$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^6)$。

输出格式

输出一个整数，表示对于所有 $1 \le l \le r \le n$，$mi(l, r) \times sum(l, r)$ 的最大值。

样例

6
3 1 6 4 5 2

60

说明/提示

样例解释

取 $l = 3, r = 5$，则 $mi(3, 5) \times sum(3, 5) = \min(6, 4, 5) \times (6 + 4 + 5) = 4 \times 15 = 60$。

数据规模与约定

• 对于 $30\%$ 的数据，$n, a_i \le 100$
• 对于 $60\%$ 的数据，$n, a_i \le 1000$
• 对于 $100\%$ 的数据，$1 \le n \le 10^5, 1 \le a_i \le 10^6$