题面：this
solution:
容斥神仙题qwq
考虑全集-补集，此时补集就是一些集合的并，可使用容斥
设至少 \(j\) 个点满足 \(b[i]==b[i+1]\) 时方案数为 \(f_j\)
直接求不好求，考虑转化:
有 \(j\) 个点时就把原序列隔成了 \(n-j\) 段，段内无所谓，但是用于分割的之间的段需要一样
此时自然而然的可以定义出：\(f_{i,j}\) 为考虑前 \(i\) 个数，隔成 \(j\) 段时的方案
所以此时可以设计出一个状态转移方程：
\[f_{i,j}=\sum^{i-1}_{k=1}\min^{i}_{k} \times f_{k,j-1} \]时间复杂度为 \(O(n^3)\)。
此时可以发现：\(j\) 的具体值对答案没有任何影响，只有奇偶性有影响
所以可以把第二维压成 \(1/0\),此时时间复杂度降到 \(O(n^2)\)
接着观察一下式子，发现 \(\min\) 很难搞。
接下来关键的一步，就是回到 \(dp\) 的状态转移，\(dp\) 的关键是从子状态转移到现在的状态。
因此，考虑拆 \(\min\)：
可以发现一个性质：
对于一个下标 \(i\)，找到最右边的 \(j<i\) 并同时满足 \(a[j]<a[i]\)，那么有：
\[f_{i,x}=f_{j,xxor1}+a[i]\sum^{i}_{k=j+1}f_{k,x} \]此时维护一个单调栈即可在 \(O(n)\) 时间复杂度转移
code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=998244353;
int n,a[N];
int stk[N],top;
int f[N][2],s[N][2];
signed main(){
std::ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
f[0][0]=s[0][0]=1,f[0][1]=s[0][1]=0;
for(int i=1;i<=n;i++){
while(a[stk[top]]>=a[i]&&top)top--;
stk[++top]=i;
for(int j=0;j<2;j++){
f[i][j]=((top==1?0:f[stk[top-1]][j])+(s[i-1][j^1]-(top==1?0:s[stk[top-1]-1][j^1])+mod)*a[i])%mod;
s[i][j]=(s[i-1][j]+f[i][j])%mod;
}
}
cout<<(f[n][0]-f[n][1]+mod)*((n&1)?(-1+mod):1)%mod;
return 0;
}