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 Rectangle {
  int height;
  int pos;
};
int getLargestRectangle(int size, int buffer[]) {
  stack<Rectangle> S;
  int maxv = 0;
  buffer[size] = 0;
  for (int i = 0; i <= size; i++) {
    Rectangle rect;
    rect.height = buffer[i];
    rect.pos = i;
    if (S.empty() || S.top().height < rect.height)
      S.push(rect);
    else if (S.top().height > rect.height) {
      int target = i;
      while (!S.empty() && S.top().height >= rect.height) {
        Rectangle pre = S.top();
        S.pop();
        int area = pre.height * (i - pre.pos);
        maxv = max(maxv, area);
        target = pre.pos;
      }
      rect.pos = target;
      S.push(rect);
    }
  }
  return maxv;
}
int H, W;
int buffer[1400][1400];
int T[1400][1400];
int getLargestRectangle() {
  for (int j = 0; j < W; j++)
    for (int i = 0; i < H; i++)
      if (buffer[i][j])
        T[i][j] = 0;
      else
        T[i][j] = (i > 0) ? T[i - 1][j] + 1 : 1;
  int maxv = 0;
  for (int i = 0; i < H; i++) maxv = max(maxv, getLargestRectangle(W, T[i]));
  return maxv;
}
int main() {
  scanf("%d", &W);
  H = 1;
  for (int i = 0; i < H; i++)
    for (int j = 0; j < W; j++) scanf("%d", &buffer[i][j]);
  cout << getLargestRectangle() << endl;
}
