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 ll;
const int N = 1<<17;// = 131072
const ll INF = (1e9)+10;

/*dat???????????????N?????????*/

class RMQ{
public:
  ll n,dat[2*N-1];

  //?????????
  RMQ(){
    n=N;
    for(int i=0;i<2*n-1;i++) dat[i]=INF;
  }
  
  //k???????????????a????????´
  void update(int k,ll a){
    k+=n-1;
    dat[k]=a;
    while(k>0){
      k=(k-1)/2;
      dat[k]=min(dat[k*2+1],dat[k*2+2]);
    }
  }
  
  //[a,b)???????°????????±??????? query(a,b,0,0,n)
  ll query(int a,int b,int k=0,int l=0,int r=N){
    if(r<=a||b<=l)return INF;
    if(a<=l&&r<=b)return dat[k];

    ll vl=query(a,b,k*2+1,l,(l+r)/2);
    ll vr=query(a,b,k*2+2,(l+r)/2,r);
    return min(vl,vr);
  }
};


ll n,A[N];
vector<int>Idx;
ll L[N],R[N];


void calc(ll arr[]){
  RMQ rmq;
  for(int i=0;i<n;i++){
    int idx = lower_bound(Idx.begin(),Idx.end(),A[i]) - Idx.begin();
    ll val = -rmq.query(0,idx); //A[i]???????°???????????????§?????§???index?????????
    if(val == -INF) val = -1;

    arr[i] = i - val - 1;
    rmq.update(idx,-i);
  }
}

int main(){
  cin>>n;
  Idx.resize(n);
  for(int i=0;i<n;i++)cin>>A[i],Idx[i] = A[i];
  sort(Idx.begin(),Idx.end());
  Idx.erase(unique(Idx.begin(),Idx.end()),Idx.end());
  
  calc(L);
  reverse(A,A+n);
  calc(R);
  reverse(A,A+n);

  ll ans=0;
  for(int i=0;i<n;i++){
    ll w = L[i]+R[n-1-i]+1;
    ans = max(ans,w*A[i]);
  }
  cout<<ans<<endl;
  return 0;
}