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;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

int n, h[100010], l[100010], r[100010], st[100010];
signed main(void)
{
  cin >> n;
  REP(i, n) cin >> h[i];
  int t = 0;
  REP(i, n) {
    while(t>0 && h[st[t-1]] >= h[i]) t--;
    l[i] = t == 0 ? 0 : (st[t-1]+1);
    st[t++] = i;
  }
  t = 0;
  for(int i=n-1; i>=0; --i) {
    while(t > 0 && h[st[t-1]] >= h[i]) t--;
    r[i] = t == 0 ? n : st[t-1];
    st[t++] = i;
  }
  ll ret = 0;
  REP(i, n) ret = max(ret, (ll)h[i]*(r[i]-l[i]));
  cout << ret << endl;
  return 0;
}