单调栈求出每个位置x左边第一个大于它的位置L[x]和右第一个不小于它的位置R[x]，于是矩形L[x]<=l<=x<=r<=R[x]内的点(l,r)对应的区间[l,r]的最值为x位置的值，这个矩形内的点只对答案数组的二阶差分的四个位置有影响，可以全部统计后再求两次前缀和得到答案。
#include<bits/stdc++.h>
typedef long long i64;
const int N=1e6+,P=;
char ib[N*],*ip=ib;
int _(){
int x=;
while(*ip<)++ip;
while(*ip>)x=x*+*ip++-;
return x;
}
int n,a[N],ss[N],ls[N],rs[N],sp=;
i64 s[N];
int main(){
fread(ib,,sizeof(ib),stdin);
n=_();
for(int i=;i<=n;++i)a[i]=_();
a[]=a[n+]=0x7fffffff;
for(int i=;i<=n+;++i){
while(sp&&a[ss[sp]]<a[i])rs[ss[sp--]]=i-;
ss[++sp]=i;
}
sp=;
for(int i=n;i>=;--i){
while(sp&&a[ss[sp]]<=a[i])ls[ss[sp--]]=i+;
ss[++sp]=i;
}
for(int i=;i<=n;++i){
int x=i-ls[i]+,y=rs[i]-i+;
if(x>y)std::swap(x,y);
s[]+=a[i];
s[x]-=a[i];
s[y]-=a[i];
s[x+y]+=a[i];
}
s[]%=P;
for(int i=;i<n;++i)(s[i]+=s[i-])%=P;
for(int i=;i<n;++i)(s[i]+=s[i-])%=P;
int ans=;
for(int i=;i<n;++i)ans^=s[i]<?s[i]+P:s[i];
printf("%d\n",ans);
return ;
}