Describe

Alice has a magic array. She suggests that the value of a interval is equal to the sum of the values in the interval, multiplied by the smallest value in the interval.

Now she is planning to find the max value of the intervals in her array. Can you help her?

Input

First line contains an integer n(1≤n≤5*10^5)

Second line contains

Output

One line contains an integer represent the answer of the array.

5

1 2 3 4 5

36

#include<cstdio>
#include <algorithm>
using namespace std;
int arr[5 * (int)(10e5) + 10];
int dp[5 * (int)(10e5) + 10];
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
dp[0] = arr[0];
for (int i = 1; i < n; i++)//前i个数
{
int sum = arr[i];
for (int j = 1; j <= i; j++)
{
sum += arr[i - j];
dp[i] = max(dp[i],max(dp[i - 1], *min_element(arr + (i - j),arr+i+1)*sum));
}
dp[i] = max(dp[i], arr[i]);
}
printf("%d", dp[n - 1]);
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 500000+10;
const LL inf = 1e17;

int n;
int i,j;
LL sum[maxn],stmx[maxn][23],stmn[maxn][23];
int a[maxn],l[maxn],r[maxn];

stack<int> sta;

{
int k=log2(r-l+1);
return max(stmx[l][k],stmx[r-(1<<k)+1][k]);
}

{
int k=log2(r-l+1);
return min(stmn[l][k],stmn[r-(1<<k)+1][k]);
}

int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<=n;i++) sum[i]=sum[i-1]+(LL)a[i];
for (i=0;i<=n;i++) stmx[i][0]=stmn[i][0]=sum[i];
for (j=1;(1<<j)<=n+1;j++)
{
for (i=0;i+(1<<j)-1<=n;i++)
{
stmx[i][j]=max(stmx[i][j-1],stmx[i+(1<<(j-1))][j-1]);
stmn[i][j]=min(stmn[i][j-1],stmn[i+(1<<(j-1))][j-1]);
}
}
for (i=1;i<=n;i++)
{
while (!sta.empty()&&a[i]<=a[sta.top()]) sta.pop();
if (sta.empty()) l[i]=1; else l[i]=sta.top()+1;
sta.push(i);
}
while (!sta.empty()) sta.pop();
for (i=n;i>=1;i--)
{
while (!sta.empty()&&a[i]<=a[sta.top()]) sta.pop();
if (sta.empty()) r[i]=n; else r[i]=sta.top()-1;
sta.push(i);
}
LL ans=-inf;
for (i=1;i<=n;i++)
{
if (a[i]<0)
{
ans=max(ans,(R-L)*(LL)a[i]);
} else
if (a[i]>0)
{
}