A histogram is made of a number of contiguous bars, which have same width.

For a given histogram with $N$ bars which have a width of 1 and a height of $h_i$ = $h_1, h_2, ... , h_N$ respectively, find the area of the largest rectangular area.

Constraints

* $1 \leq N \leq 10^5$
* $0 \leq h_i \leq 10^9$

Input

The input is given in the following format.

$N$
$h_1$ $h_2$ ... $h_N$

Output

Print the area of the largest rectangle.

Examples

Input

8
2 1 3 5 3 4 2 1


Output

12


Input

3
2 0 1


Output

2


#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include<vector>
#include<cstring>
#include<set>
#include <cstdio>
#include<queue>
#include<map>
#define WHITE 0
#define GRAY  1
#define BLACK 2
#define endl '\n'
#define forup(i,a,n) for( int i =a; i < n; i++)
#define llforup(i,a,n) for( ll i =a; i < n; i++)
#define fordown(i,a,n) for( int i =a; i >= n; i--)
#define fornot(i,a,n) for( int i=a;!n;i++)
#define mod  (ll)(1e9+7)
#define ifempty(a)  if(!a)
using namespace std;
typedef long long ll;
inline int readnum()
{
	int p, data = 0; char ch = 0;
	while ((ch != ' - ') && ch < '0' || ch>'9') ch = getchar();//相当于正则表达式的搜索，跳过不需要的字符
	if (ch == '- ')p = -1, ch = getchar();
	else p = 1;
	while (ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = getchar();//搜索需要的字符
	return data * p;
}
//E-mail 374656045@qq.com
#define MAX (unsigned)1e5+1
struct Rectangle { int pos; ll height; };
Rectangle stack[MAX];
class solve {
private:
	int tot; int top = 0; int temp; ll area;//防溢出
	ll maxv=0;
	char ch;
public:
	solve()
	{
		tot = read();
		stack[top].height = read();
		for (int i = 1; i <= tot; i++)
		{
			temp = read();
			if (temp > stack[top].height) { stack[++top].height = temp; stack[top].pos = i; }
			else if (temp < stack[top].height)
			{
				while (temp < stack[top].height)
				{
					area = stack[top].height * (i - stack[top].pos);
					top--;
					if (area > maxv)maxv = area;
					if (top == -1)break;//边界检查
				}
				stack[++top].height = temp;
			}
		}
		printf("%lld\n", maxv);
	}
	inline int read()//正数版
	{
		int data = 0;
		ch = getchar();
		while (ch != ' '&&ch!='\n'&& ch!=EOF)
		{
			data = data * 10 + ch - '0';
			ch = getchar();
		}
		return data;
	}


};
int main(void)
{
	//ios_base::sync_with_stdio(0); cin.tie(0);//慎用，cin和scanf混用会导致非MSC++WA
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	solve solution;
#ifdef DEBUG
	fclose(stdin);//关闭文件 
	fclose(stdout);//关闭文件 
#endif
	return 0;

}


