解法

• 元素x对答案如果产生了贡献，那么比x大的数字都在x的后面。
• x成为天选之子，概率为1/(n-x+1)
• 独立考虑每个元素对答案的贡献，所以答案为sigma 1/i,其中i: 1->n

做法： Meow

做法：

设f(L,R)表示max(a[L~R])-min(a[L,R])

• 逐个枚举左端点
• 逐个枚举右端点

然后，我们发现逐个枚举右端点很辣鸡的。

我们用单调栈，维护在元素i后面的第一个大于a[i]的元素，与第一个小于a[i]的元素。

确定L，我们就可以把f(L,R)相等的R一起处理了。

复杂度O(NlogN),因为对1/x积分可知：1/1+1/2+...+1/n ~ log N

code

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int N = 100000+10;pair
        
          stk[N]; int top;int T, n, a[N], nex1[N], nex2[N];long long cnt[N];void brute() {    long long sum[N]={0};    for(int i=1;i<=n;i++){        int mx=-1,mn=N;        for(int j=i;j<=n;j++){            mx=max(mx,a[j]); mn=min(mn,a[j]);            sum[mx-mn]++;            if(mx-mn==2) printf("[%d,%d]\n", i,j);        }    }    for(int i=1;i<=n;i++){        sum[i]+=sum[i-1];    }    for(int i=0;i
         
          =1;i--) { while(a[i]>stk[top].first) top--; nex1[i]=stk[top].second; stk[++top]=make_pair(a[i],i); } top=0; stk[++top]=make_pair(0, n+1); for(int i=n;i>=1;i--) { while(a[i]