本文共 839 字，大约阅读时间需要 2 分钟。

维护最小值只需要把原来数组全部变成相反数，可以找到最小值。

求和：排列组合的思想，当前数作为最大值，左边到l[i] ,右边到r[i]，左边的情况有i-l[i]种，右边情况有r[i]-i种，相乘即可。

#include
   
    using namespace std;#define int long long int a[1<<17];int l[1<<17],r[1<<17];int n;int  solve(){        for(int i=1;i<=n;i++){               int j=i;            while(j>1 && a[j-1]<=a[i]) //当前数与前面的数进行比较                    j=l[j-1];            l[i]=j;        }        for(int i=n;i;i--){               int j=i;            while(j
    
     >t;    while(t--){           cin>>n;        for(int i=1;i<=n;i++) cin>>a[i];        int ans=solve();        for(int i=1;i<=n;i++) a[i]=-a[i];        cout<
     
      <