这题是典型的单调栈的题目。这里说说我对单调栈的理解：单调栈就是在一个栈里面维持单调的性质，即单调增或者单调递减。如果是单调增的话，准备入栈的元素和栈顶作比较，如果大于
栈顶，就入栈；否则就将栈顶元素退栈，在用新的栈顶元素和入栈元素比较，直到入栈元素大于栈顶元素。
这道题就是求出一个数在一个最大的区间内使得该数是区间内最小。所以需要求出每一个数所能扩展区间的右端点和左端点。单调栈就是用来维护这两个端点的。
在一个准备入栈的数和栈顶元素比较时，如果栈顶元素较小而退栈，此时退栈的数的右端点就是准备入栈的数的位置的前一位，而左端点是其在栈中的下一个元素的位置的后一位（当然需要
留意数组中的第一个和最后一个元素的处理）。当栈只剩下一个元素时，最后一个元素的左端点就是1.
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<list>
#include<stack>
using namespace std;
struct pnt
{
int ls,rs,val,biao; //ls是左端点，rs是右端点，val是值，biao代表位置
}a[100050];
long long sum[100050];
void init(int n)
{
sum[0]=0;
for(int i=1;i<=n;i++)
{
a[i].biao=i;
sum[i]=sum[i-1]+a[i].val;
}
}
stack<pnt> sta;
void work(int n)
{
sta.push(a[1]);
int minn,tem;
pnt top,final;
bool push_not;
for(int i=2;i<=n;i++)
{
push_not=0;
minn=sta.top().val;
tem=a[i].val;
if(tem>minn) sta.push(a[i]); //大于栈顶就入栈
else //否则，栈顶元素退栈
{
while(!sta.empty())
{
if(tem<=sta.top().val)
{
top=sta.top();
sta.pop();
a[top.biao].rs=i-1;
if(sta.empty()) a[top.biao].ls=1;
else a[top.biao].ls=sta.top().biao+1;
}
else { sta.push(a[i]);push_not=1;break;}
}
if(push_not==0) sta.push(a[i]);
}
}
final=sta.top();
sta.pop();
a[final.biao].rs=n;
if(sta.empty()) a[final.biao].ls=1;
else a[final.biao].ls=sta.top().biao+1;
while(!sta.empty()) //最后符合单调性质的栈，右端点都是数组的最后一位
{
top=sta.top();
sta.pop();
if(sta.empty())
{
a[top.biao].ls=1;
a[top.biao].rs=final.biao;
}
else
{
a[top.biao].ls=sta.top().biao+1;
a[top.biao].rs=final.biao;
}
}
}
int main()
{
int n;
long long maxn=-1;//在这道题中maxn要初始为小于0的数
int ls,rs;
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].val);
}
init(n);
work(n);
for(int i=1;i<=n;i++)
{
//cout<<"a["<<i<<"].ls="<<a[i].ls<<" rs="<<a[i].rs<<" val="<<a[i].val<<endl;
long long tem=(sum[a[i].rs]-sum[a[i].ls-1])*a[i].val;
if(tem>maxn) { maxn=tem;ls=a[i].ls; rs=a[i].rs;}
}
//cout<<biao<<endl;
cout<<maxn<<endl;
cout<<ls<<' '<<rs<<endl;
}