U126093.连续段落智力水平最大

现在有 $n$ 个人，每个人都有一个智力数值 $w_i$，特别的，小明规定：从第 $i$ 个人到第 $j$ 个人的总智力水平为：$i$ 到 $j$ 中最低的智力数值乘以 $i$ 到 $j$ 所有人的智力之和，即 $\sum_{i,j} \min\bigl(w[i], w[i+1], \dots, w[j]\bigr)$
小明准备从 $n$ 个人中选出连续的一段，使得这段人的总智力水平最大，你能帮助他吗？

第一行一个整数 $n$ 代表有 $n$ 个人。
第二行 $n$ 个整数分别对应 $w_1,w_2,\cdots,w_{n-1},w_n$ 代表每个人的智力

输出一个整数，表示最大的智力水平数值。

对于 $100\%$ 的数据 $1 \le n \le 10^5$ $1 \le w_i \le 10^6$