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;
typedef long long int ll;

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    int N;
    Scd(N);

    vl h(N);
    Rep(i,N) Scll(h[i]);

    stack<int> s;
    vl l(N);
    vl r(N);

    int tmp = 0;
    deque<int> q;

    Rep(i,N){
        while( s.size() && h[s.top()] >= h[i] ) s.pop();
        // tmp = s.size();
        // Rep(k,tmp) printf("%d,", s.top() ), q.push_back(s.top()), s.pop();
        // Rep(k,tmp) s.push(q.back()), q.pop_back();
        // printf ("\n");
        l[i] = s.empty() ? 0 : s.top()+1;
        s.push(i);
    }
    while( s.size() ) s.pop();
    while( q.size() ) q.pop_front();
    RRep(i,N){
        while( s.size() && h[s.top()] >= h[i] ) s.pop();
        // tmp = s.size();
        // Rep(k,tmp) printf("%d,", s.top() ), q.push_back(s.top()), s.pop();
        // Rep(k,tmp) s.push(q.back()), q.pop_back();
        // printf ("\n");
        r[i] = s.empty() ? N : s.top();
        s.push(i);
    }

    ll ans = 0;
    Rep(i,N){
        // printf ("(%lld-%lld)*%lld\n", r[i], l[i], h[i] );
        ans = max( ans, (r[i]-l[i])*h[i] );
    }

    printf ("%lld\n", ans );

    return 0;
}


