题意：给水平上n条垂线的长度，选择其中两条线围成梯形，求出最大的梯形面积。
题解：首先贪心分析一下，要使面积最大，尽量使高（两条线水平距离）和两底（两条线长度）更大，所以我们可以先预处理出两组线，一组表示取出来放在左边的线，一组表示放在右边的线。
我们分析一下从左边取出一条怎样的线才是好的。
第一，它应该要靠左，这样可以使高更大。
第二，它长度应该长，这样可以使底更长。
对于靠右且长度还没其他边长的边就应该去除，这里我们可以用单调栈处理（右边同理）。
现在我们再考虑暴力加剪枝的方法写这个题。
我们算左边的线某条线now的贡献，暴力找到右边使面积最大的线p。
对于now来说，p-1的线高不够，p+1的线底不够。
那么对于now+1来说， p-1的贡献也必然不如p，因为我缺的是高，给我更长一点的底没有意义。
对于now-1，同理。
所以对于比now大的边，我没有必要再查比p小的边了，比now小的边，也没必要查比p大的边了。
这里就可以用分治解决了，时间复杂度类似于快速排序，但不会被特殊样例卡时间，因为对于左边的线l至r每次稳定减半。
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
#define ll long long
const ll N=1e6+7;
ll n,a[N],ans;
stack<ll>sa;
vector<ll>ho,aq;
ll cal(ll x,ll y){
ll p=aq[x];
ll P=ho[y];
return (P-p)*(a[P]+a[p]);
}
void gao(ll l,ll r,ll L,ll R){
if(l>r){
return;
}
ll mid=(l+r)/2;
ll p=L;
for(int i=L;i<=R;i++){
if(cal(mid,p)<cal(mid,i)){
p=i;
}
}
ans=max(ans,cal(mid,p));
gao(l,mid-1,L,p);
gao(mid+1,r,p,R);
}
int main(){
ho.push_back(0);
aq.push_back(0);
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;i++){
while(!sa.empty()){
ll p=sa.top();
if(a[p]<=a[i]){
sa.pop();
}
else{
break;
}
}
sa.push(i);
}
while(!sa.empty()){
ho.push_back(sa.top());
sa.pop();
}
for(int i=n;i>=1;i--){
while(!sa.empty()){
ll p=sa.top();
if(a[p]<=a[i]){
sa.pop();
}
else{
break;
}
}
sa.push(i);
}
while(!sa.empty()){
aq.push_back(sa.top());
sa.pop();
}
sort(ho.begin(),ho.end());
sort(aq.begin(),aq.end());
gao(1,aq.size()-1,1,ho.size()-1);
printf("%lld
",ans);
}