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 rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
const ll inf = 1e16;
const ll md = 1000000007;
void solve(int n,vll aa){
  vector<pair<ll,ll>> stack;
  vll itol(n),itor(n);
  //高さ、アドレスの順
  stack.emplace_back(0,0);
  rep(i,n){
    while(stack.size() && stack.back().first>=aa[i]) stack.pop_back();
    if(stack.size()) itol[i]=stack.back().second;
    stack.emplace_back(aa[i],i+1);
  }
  stack.clear();
  stack.emplace_back(0,n);
  for (int i=n-1;i>=0;i--){
    while(stack.size() && stack.back().first>=aa[i]) stack.pop_back();
    if(stack.size()) itor[i]=stack.back().second;
    stack.emplace_back(aa[i],i);
  }
  //rep(i,n) cout<<itol[i]<<" ";
  //cout<<endl;
  //rep(i,n) cout<<itor[i]<<" ";
  //cout<<endl;
  ll ans=0;
  rep(i,n) ans=max(ans,aa[i]*(itor[i]-itol[i]));
  cout<<ans<<endl;
}

int main() {
  int n;
  cin>>n;
  vll aa(n);
  rep(i,n) cin>>aa[i];
  solve(n,aa);  
  return 0;
}

