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;
struct Edge {
  int s, t, w;
  Edge(int s, int t, int w) : s(s), t(t), w(w) {}
  Edge() : Edge(-1, -1, -1) {}
  bool operator<(const Edge& e) const {
    return w != e.w ? w < e.w : (s != e.s ? s < e.s : t < e.t);
  }
};
struct P {
  double x, y;
  P(double x, double y) : x(x), y(y) {}
  P() : P(0, 0) {}
  P operator+(const P& v) const { return P(x + v.x, y + v.y); }
  P operator-(const P& v) const { return P(x - v.x, y - v.y); }
  P operator*(const double v) const { return P(x * v, y * v); }
  bool operator==(const P& v) const {
    return abs(x - v.x) <= 0.0000000000001 && abs(y - v.y) <= 0.00000000000001;
  }
  bool operator!=(const P& v) const {
    return abs(x - v.x) > 0.0000000000001 || abs(y - v.y) > 0.00000000000001;
  }
  double dot(const P& v) const { return x * v.x + y * v.y; }
  double cross(const P& v) const { return x * v.y - y * v.x; }
  double length() const { return sqrt(x * x + y * y); }
  double length2() const { return (x * x + y * y); }
  bool operator<(const P& v) const { return x < v.x || (x == v.x) && y < v.y; }
  bool operator>(const P& v) const { return x > v.x || (x == v.x) && y > v.y; }
};
struct Rectangle {
  int h, p;
  Rectangle(int h, int p) : h(h), p(p) {}
};
int h[100000];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> h[i];
  }
  stack<Rectangle> rs;
  int ans = 0;
  for (int i = 0; i < N; i++) {
    if (rs.empty()) {
      rs.push(Rectangle(h[i], i));
    } else {
      if (rs.top().h < h[i]) {
        rs.push(Rectangle(h[i], i));
      } else if (rs.top().h > h[i]) {
        int tp = i;
        while (!rs.empty() && rs.top().h > h[i]) {
          Rectangle tr = rs.top();
          rs.pop();
          ans = max(ans, tr.h * (i - tr.p));
          tp = tr.p;
        }
        rs.push(Rectangle(h[i], tp));
      }
    }
  }
  while (!rs.empty()) {
    Rectangle tr = rs.top();
    rs.pop();
    ans = max(ans, tr.h * (N - tr.p));
  }
  cout << ans << endl;
  return 0;
}
