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 rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;

const int mod = (int)1e9 + 7;
void dbg(){ cerr << "\n"; } template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

ll max_rectangle(const vector<int>& vec) {
	ll rtn = 0;
	stack<pii> stk;
	auto calstk = [&](int ps, int ht){
		int t = ps;
		for( ;!stk.empty() && stk.top().second >= ht; stk.pop()){
			if(stk.top().second == ht) return;
			t = stk.top().first;
			rtn = max(rtn, 1LL * (ps-t) * stk.top().second);
		}
		if(ht >0 ) stk.push(pii(t, ht));
	};
	rep(i, sz(vec)){
		calstk(i, vec[i]);
	}
	calstk(sz(vec), 0);
	return rtn;
}


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

	int n; cin >>n;
	VI a(n);
	rep(i, n) cin >> a[i];
	
	cout << max_rectangle(a) <<"\n";
	
	return 0;
}

