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 "bits/stdc++.h"

#define INF 99999999
#define FER 0.0000000001

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;

struct Edge
{
	int s, t, w;
	Edge(int s,int t,int w):s(s),t(t),w(w){}
	Edge() :Edge(-1, -1, -1) {}
	bool operator<(const Edge& e)const
	{
		return w != e.w ? w < e.w : (s != e.s ? s < e.s : t < e.t);
	}
};


struct P
{
	double x, y;
	P(double x, double y) :x(x), y(y) {}
	P() :P(0, 0) {}
	P operator+(const P& v)const
	{
		return P(x + v.x, y + v.y);
	}
	P operator-(const P& v)const
	{
		return P(x - v.x, y - v.y);
	}
	P operator*(const double v)const
	{
		return P(x*v, y*v);
	}
	bool operator==(const P& v)const
	{
		return abs(x - v.x) <= 0.0000000000001&&abs(y - v.y) <= 0.00000000000001;
	}
	bool operator!=(const P& v)const
	{
		return abs(x - v.x) > 0.0000000000001 || abs(y - v.y) > 0.00000000000001;
	}

	double dot(const P& v)const
	{
		return x*v.x + y*v.y;
	}
	double cross(const P& v)const
	{
		return x*v.y - y*v.x;
	}
	double length()const
	{
		return sqrt(x*x + y*y);
	}
	double length2()const
	{
		return (x*x + y*y);
	}

	bool operator<(const P& v)const
	{
		return x<v.x || (x == v.x) && y < v.y;
	}
	bool operator>(const P& v)const
	{
		return x>v.x || (x == v.x) && y > v.y;
	}
};

struct Rectangle
{
	ll h;
	int p;
	Rectangle(ll h,int p):h(h),p(p){}
};

ll h[100001];

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> h[i];
	}
	h[N++] = 0;

	stack<Rectangle> rs;

	ll ans = 0;
	for (int i = 0; i < N; i++)
	{
		if (rs.empty())
		{
			rs.push(Rectangle(h[i], i));
		}
		else
		{
			if (rs.top().h < h[i])
			{
				rs.push(Rectangle(h[i], i));
			}
			else if (rs.top().h>h[i])
			{
				int tp = i;
				while (!rs.empty() && rs.top().h>h[i])
				{
					Rectangle tr = rs.top();
					rs.pop();
					ans = max(ans, tr.h*(i - tr.p));
					tp = tr.p;
				}
				rs.push(Rectangle(h[i], tp));
			}
		}
	}

	cout << ans << endl;

	return 0;
}
