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 <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 2000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
#define seg_size 524288
int grid[2][200000] = {};
long long memorize[2][200000] = {};
int main() {
#define int long long
	int h, w;
	cin >> w;
	h = 1;
	REP(i, h) {
		REP(q, w) {
			cin >> grid[i][q];
		}
	}
	for (int i = 0;i < w;++i) {
		int cnt = 0;
		for (int q = 0;q < h;++q) {
			memorize[q][i] = grid[q][i];
		}
	}
	long long ans = 0;
	for (int i = 0;i < h;++i) {
		stack<pair<int, int>> wow;
		for (int q = 0;q <= w;++q) {
			if (wow.empty() == true || wow.top().first < memorize[i][q]) {
				wow.push(make_pair(memorize[i][q], q));
			}
			else {
				int itring = q;
				while (wow.empty() == false && wow.top().first > memorize[i][q]) {
					ans = max(ans, (q - wow.top().second)*wow.top().first);
					itring = min(itring, wow.top().second);
					wow.pop();
				}
				wow.push(make_pair(memorize[i][q], itring));
			}
		}
	}
	cout << ans << endl;
	return 0;
}
