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>
struct rect {
  long long int height;
  long long int pos;
};
long long int table[100001];
int large_histogram(long long int w);
int main(void) {
  long long int i, j, w, temp, max = 0;
  scanf("%lld", &w);
  for (i = 0; i < w; i++) scanf("%lld", &table[i]);
  temp = large_histogram(w);
  if (max < temp) max = temp;
  printf("%lld\n", max);
}
int large_histogram(long long int w) {
  long long int i, sp = 0, max = 0;
  struct rect stack[100001];
  table[w] = 0;
  for (i = 0; i <= w; i++) {
    struct rect r;
    r.height = table[i];
    r.pos = i;
    if (!sp || stack[sp - 1].height < r.height)
      stack[sp++] = r;
    else if (stack[sp - 1].height > r.height) {
      long long int target = i;
      while (sp && stack[sp - 1].height >= r.height) {
        struct rect pre = stack[--sp];
        long long int area = pre.height * (i - pre.pos);
        if (max < area) max = area;
        target = pre.pos;
      }
      r.pos = target;
      stack[sp++] = r;
    }
  }
  return max;
}
