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;
int main() {
  int n;
  cin >> n;
  vector<int> h(n);
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }
  if (n == 1) {
    cout << h[0] << endl;
    return 0;
  }
  stack<int> pos, height;
  int maxval = 0;
  for (int i = 0; i < n; i++) {
    if (pos.empty() || i == n - 1 || height.top() < h[i]) {
      pos.push(i);
      height.push(h[i]);
    }
    if (height.top() > h[i] || i == n - 1) {
      int tmpp = pos.top(), tmph = height.top();
      height.pop();
      maxval = max(maxval, tmph * (i - tmpp));
      while (!height.empty() && height.top() > h[i]) {
        pos.pop();
        tmpp = pos.top();
        tmph = height.top();
        height.pop();
        maxval = max(maxval, tmph * (i - tmpp));
      };
      height.push(h[i]);
    }
  }
  maxval = max(maxval, height.top() * (n - 1 - pos.top()));
  cout << maxval << endl;
  return 0;
}
