题目描述 给定一个长度为 n 的正整数数组 a，按照分治规则计算答案：

将当前区间 [l,r] 以中点 mid 拆分为左区间 [l,mid] 和右区间 [mid+1,r]； 计算左区间最大值 × 右区间最小值，将结果累加到总答案； 递归处理左、右子区间； 区间长度为 1 时，递归终止。

递归边界：区间长度为 1 时，无左右子区间，贡献为 0； 区间拆分：用中点 mid 将数组平分为左右两部分； 贡献计算：遍历左区间求最大值，遍历右区间求最小值，计算乘积； 递归累加：递归处理左右子区间，将所有贡献累加得到最终答案。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,ans=0;
int a[200100];
// 计算区间[l,r]的总贡献
int dfs(int l,int r){
    // 递归边界：单个元素无贡献
    if(l==r){
        return 0;
    }
    int mid=(l+r)/2;
    //记录最大最小值
    int maxn=0,minn=1e9;
    // 遍历左区间求最大值
    for(int i=l;i<=mid;i++){
        maxn=max(maxn,a[i]);
    }
    // 遍历右区间求最小值
    for(int i=mid+1;i<=r;i++){
        minn=min(minn,a[i]);
    }
   
    // 当前贡献 + 左子区间贡献 + 右子区间贡献
    return maxn*minn+dfs(l,mid)+dfs(mid+1,r);
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    cout<<dfs(1,n);
    return 0;
}