南昌ネット試合Max Answer

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\le n\le 5\times 10 ^5n(1≤n≤5×10 ^5). Second line contains nn integers represent the array a(−10^5 ≤a i≤10^5 ). Output One line contains an integer represent the answer of the array. サンプル入力コピー5 1 2 3 4 5サンプル出力コピー36

#include
#include
#include
#include
using namespace std;
const int N=5*1e5+10;
long long dpmin[N][21],dpsumx[N][21],dpsumd[N][21],a[N],sum[N];int n;
void ST1()
{
	for(int i=1;i<=n;i++)dpmin[i][0]=a[i];
		for(int j=1;(1<0)maxn=max(slove(i),maxn);
		else maxn=max(slove2(i),maxn);
	}
	printf("%lld
",maxn);
}

rmqで区間の最小値をクエリーし、正数に対しては区間の最小値を満たす最大区間(二分で左右の端点を求める)を見つけるだけで、負数に対しては区間と最小値を見つけ、二分接頭辞と解を求める