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;
const int N = 1 << 17;
const long long INF = (1e9) + 10;
class RMQ {
 public:
  long long n, dat[2 * N - 1];
  RMQ() {
    n = N;
    for (int i = 0; i < n; i++) dat[i] = INF;
  }
  void update(int k, long long 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]);
    }
  }
  long long 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];
    long long vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    long long vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return min(vl, vr);
  }
};
long long n, A[N], Idx[N];
long long L[N], R[N];
void calc(long long arr[]) {
  RMQ rmq;
  for (int i = 0; i < n; i++) {
    int idx = lower_bound(Idx, Idx + n, A[i]) - Idx;
    long long val = -rmq.query(0, idx);
    if (val == -INF) val = -1;
    arr[i] = i - val - 1;
    rmq.update(idx, -i);
  }
}
int main() {
  cin >> n;
  assert(n < 15);
  for (int i = 0; i < n; i++) cin >> A[i], Idx[i] = A[i];
  sort(Idx, Idx + n);
  calc(L);
  reverse(A, A + n);
  calc(R);
  reverse(A, A + n);
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    long long w = L[i] + R[n - 1 - i] + 1;
    ans = max(ans, w * A[i]);
  }
  cout << ans << endl;
  return 0;
}
