题目描述

在一张网格图中，网格共有 $n$ 列，每列有一些格子被光头强从底向上涂了色，现在给你每一列被涂色的格子的高度 $a_i$，请你求出被涂色的格子组成的最大矩形的面积。

输入格式

第一行一个整数 $n$，表示总列数。

接下来一行共 $n$ 个数，表示每列染色的格子数。

输出格式

输出一个数，表示最大面积。

5
1 2 5 3 4

9

样例解释

第 $3、4、5$ 列可以组成 $3×3$ 的矩形，面积为 $9$。

数据规模

对于100%的数据，保证 $1≤n≤2×10^5，1≤a_i≤10^9$。