一张半边参差不齐的网格纸（网格边长均为1），有一边是完整没有破损的。现要从中剪出一片面积最大的矩形纸片。
给定网格纸中完整边的长度N（1≤N≤1000000），以及网格中每一列残存部分的高度（1≤高度≤10000），输出能够剪出的最大矩形纸片面积。
例如：N=6，每一列残存部分的高度依次为3、2、1、4、5、2，如下图所示：
可以发现，沿着红色框可以剪出的矩形纸片面积最大，为8，所以输出8。
【输入描述】
第一行输入一个正整数N（1≤N≤1000000），表示纸片完整边的长度
第二行输入N个正整数（1≤正整数≤10000），表示每列格子残存部分的高度，两个正整数之间用一个空格隔开
【输出描述】
输出一个正整数，表示能够剪出的最大矩形纸片面积
【样例输入】
6
3 2 1 4 5 2
【样例输出】
8
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int a[1000006],ans;//a[i]保存了第i列的高度
int st[1000006],top,t;//st为单调递增栈，保存高度递增的柱子编号
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
for(int i=1;i<=n;i++)
{
if(a[i]>a[st[top]])//如果当前柱子高度比栈顶柱子高，则列编号进栈
st[++top]=i;
else
{
//当栈不空且栈顶柱子高于当前柱子时，弹出栈顶元素
while(top>0&&a[st[top]]>=a[i])
{
t=st[top--];
ans=max(ans,(i-st[top]-1)*a[t]);//更新最大高度
}
//当前列编号进栈
st[++top]=i;
}
}
//遍历完序列后，弹出栈内剩余柱子
//栈内剩余柱子的右边界默认为序列的最大长度
while(top>0)
{
t=st[top--];
ans=max(ans,(n-st[top])*a[t]);
}
cout<<ans;
return 0;
}