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 ll long long
#define pb push_back
ll rpa[1000000];
ll lpa[1000000];

int main()
{
    bool flag=true;
    
        memset(rpa,0,sizeof rpa);
        memset(lpa,0,sizeof lpa);


        int a;
        cin>>a;
       

        vector<ll>v;
        vector<ll>ans;
        stack<ll>s;
        stack<ll>ss;
        ll b;
        for(ll i=0;i<a;i++)
        {
            cin>>b;
            v.pb(b);
        }
        //

        s.push(0);
        for(ll ii=1;ii<a;ii++)
        {
            ll x=s.top();
            if(v[ii]>=v[x])
            {

                s.push(ii);
            }
            else
            {
                while(!s.empty() && v[ii]<v[s.top()] )
                {
                    rpa[s.top()]=ii-s.top();
                    s.pop();
                }
                s.push(ii);
            }
        }
        if(!s.empty())
        {
            while(!s.empty())
                {
                     rpa[s.top()]=a-s.top();
                     s.pop();
                }

        }
      ss.push(0);
      //lpa[0]=0;
      for(ll j=1;j<a;j++)
      {
          ll x=ss.top();
          if(v[j]>v[ss.top()])
          {
              lpa[j]=0;
              ss.push(j);
          }
          else if(v[j]==v[ss.top()])
          {
              lpa[j]=lpa[ss.top()]+1;
              ss.pop();
              ss.push(j);
          }
          else
          {
              while(!ss.empty() && v[j]<v[ss.top()])
              {
                  ss.pop();
              }
              if(!ss.empty())
              {
                  lpa[j]=j-ss.top()-1;
                  ss.push(j);
              }
              else {
                lpa[j]=j;
                ss.push(j);
              }
          }
      }
      if(!ss.empty())
      {
          while(!ss.empty())
          {
               ss.pop();
          }

      }

        for(ll k=0;k<a;k++)
        {
            ll c=(lpa[k]+rpa[k])*v[k];
            ans.pb(c);
        }
      /*  for(int jj=0;jj<a;jj++)cout<<rpa[jj]<<" ";
        cout<<endl;
        for(int l=0;l<a;l++)cout<<lpa[l]<<" ";
        cout<<endl;*/
        cout<<*max_element(ans.begin(),ans.end())<<endl;
        v.clear();
        ans.clear();


    
}

