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>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }


ll LargestRectangle(vector<ll> h){
    ll n=(ll)h.size();
    stack<pair<ll,ll>> st;//高さ，index
    st.push(make_pair(-LINF,-1));//ばんぺいくん
    ll ret=0;
    rep(i,n){
        while(h[i]<st.top().first){
            auto p=st.top();st.pop();
            chmax(ret,(i-st.top().second-1)*p.first);
        }
        st.push(make_pair(h[i],i));
    }
    while(!st.empty()){
        auto p=st.top();st.pop();
        if(p.first==-LINF) continue;
        chmax(ret,(n-st.top().second-1)*p.first);
    }
    return ret;
}


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    int n;cin>>n;
    vector<ll> h(n);
    rep(i,n){
        cin>>h[i];
    }
    cout<<LargestRectangle(h)<<endl;
    return 0;
}

