My solution
首先，我们考虑最暴力的 \(dp\)，设 \(dp_{i,j}\) 表示当前处理到第 \(i\) 位，目前序列尾部是 \(j\) 的方案数。这个 \(dp\) 的转移是很容易的。\(dp_{i,j}=\sum_{k=1}^{a_{i-1}}[k\neq j]dp_{i-1,k}\)。但是复杂度也是很寄的，是 \(O(na)\)。
然后我们考虑优化这个暴力，我们发现，因为我们每次都是用上一个的所有减去自身，所以实际上会影响某个位置的答案的只有 \(a_{i-1}\)。如果我们将所有的 \(a_i\) 离散化下来，就能得到若干个左开右闭的区间。而这个区间内的所有的 \(j\) 的转移是相同的。所以如果我们记离散化之后的第 \(i\) 个数是 \(b_i\)，\(dp_{i,j}\) 表示 \(dp\) 到第 \(i\) 位，结尾是区间 \(j\) 里的数，对于这个特定的数 的方案数。也就是，真正的“区间里所有数的方案数的总和”其实应该是 \(dp_{i,j}(b_j-b_{j-1})\)。
然后我们就得到转移 \(dp_{i,j}=\sum_{k=1}^{s_{i-1}}(b_k-b_{k-1}-[k=j])dp_{i-1,k}\)。
这样我们就得到一个 \(O(n^2)\) 的做法。但是依然过不去。
考虑优化这个算法。我们发现，\(dp_{i,j}\) 实际上就是对于上一位的所有的和减去上一次在这个位置的方案，也就是 \(totsum-dp_{i-1,j}\)，我们就可以用线段树维护 \(dp_{i,j}(b_j-b_{j-1})\)，每次转移，\(dp_{i,j}\) 先取反然后加上 \(sum\)，因为 \((b_j-b_{j-1})\) 总是不变的，所以 \(dp_{i,j}(b_j-b_{j-1})\) 也取反。对于 \(a_i\) 以上的部分，直接赋成 \(0\)。
我们可以使用乘法加法线段树，维护区间加、全局和、区间乘（\(0\) 或 \(-1\)）。我们也可以单独维护清空标记和取反标记。这里用的是第二种。
const int P=998244353;
int n,a[200005],b[200005],m;
struct node{
int l,r,len,sum,fl,tg,cl;
}sg[800005];
inline void init(int i,int l,int r){
sg[i].l=l,sg[i].r=r;
if(l==r){
sg[i].len=b[l]-b[l-1];
sg[i].sum=0;
return;
}
init(i<<1,l,(l+r)>>1);
init(i<<1|1,((l+r)>>1)+1,r);
sg[i].len=(sg[i<<1].len+sg[i<<1|1].len)%P;
}
inline void pushdown(int i){
if(sg[i].cl)sg[i].sum=0;
if(sg[i].fl)sg[i].sum=(P-sg[i].sum);
if(sg[i].tg)sg[i].sum=(sg[i].sum+1ll*sg[i].tg*sg[i].len%P)%P;
if(sg[i].l!=sg[i].r){
if(sg[i].cl)sg[i<<1].cl=1,sg[i<<1].tg=0,sg[i<<1|1].cl=1,sg[i<<1|1].tg=0;
if(sg[i].fl){
sg[i<<1].tg=(P-sg[i<<1].tg);
sg[i<<1|1].tg=(P-sg[i<<1|1].tg);
sg[i<<1].fl^=1,sg[i<<1|1].fl^=1;
}
sg[i<<1].tg=(sg[i<<1].tg+sg[i].tg)%P;
sg[i<<1|1].tg=(sg[i<<1|1].tg+sg[i].tg)%P;
}
sg[i].fl=0,sg[i].tg=0,sg[i].cl=0;
}
inline void flip(int i,int l,int r){
pushdown(i);
if(sg[i].l>r||sg[i].r<l)return;
if(sg[i].l>=l&&sg[i].r<=r){
sg[i].fl^=1;
pushdown(i);
return;
}
flip(i<<1,l,r);
flip(i<<1|1,l,r);
sg[i].sum=(sg[i<<1].sum+sg[i<<1|1].sum)%P;
}
inline void add(int i,int l,int r,int x){
pushdown(i);
if(sg[i].l>r||sg[i].r<l)return;
if(sg[i].l>=l&&sg[i].r<=r){
sg[i].tg=(sg[i].tg+x)%P;
pushdown(i);
return;
}
add(i<<1,l,r,x);
add(i<<1|1,l,r,x);
sg[i].sum=(sg[i<<1].sum+sg[i<<1|1].sum)%P;
}
inline void clear(int i,int l,int r){
pushdown(i);
if(sg[i].l>r||sg[i].r<l)return;
if(sg[i].l>=l&&sg[i].r<=r){
sg[i].cl=1;
pushdown(i);
return;
}
clear(i<<1,l,r);
clear(i<<1|1,l,r);
sg[i].sum=(sg[i<<1].sum+sg[i<<1|1].sum)%P;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
rp(i,n)cin>>a[i];
rp(i,n)b[++m]=a[i];
sort(b+1,b+1+m);
m=unique(b+1,b+1+m)-b-1;
rp(i,n)a[i]=lower_bound(b+1,b+1+m,a[i])-b;
init(1,1,m);
add(1,1,a[1],1);
rep(i,2,n){
int sum=sg[1].sum;
clear(1,a[i]+1,m);
flip(1,1,m);
add(1,1,a[i],sum);
}cout<<sg[1].sum%P<<endl;
return 0;
}
//Crayan_r
容斥
考虑容斥。
设关键点是 \(b_i=b_{i+1}\) 的情况，我们显然不需要这样的情况。所以我们需要的是恰好出现 \(0\) 个关键点的序列个数。
考虑容斥，设 \(r_k\) 表示有 \(k\) 个关键点的方案数，那么答案就是 \(\sum_{i=0}^{n-1}(-1)^kr_k\)。考虑如何快速计算。
我们发现，关键点不好计算，因为不同的关键点不是独立的。但是我们可以把相邻的关键点看作是合并，也就是把关键点转化成了对整个序列的划分。划分方案中，同一组内的一定相同，不同的可能相同。
考虑 \(dp\)，设 \(dp_{i,j}\) 表示当前 \(dp\) 到位置 \(i\)，划分出了奇数/偶数段的方案数。然后考虑转移，\(dp_{i,j}=\sum_{x=0}^{i-1}dp_{x,j\oplus 1}\min_{p=x+1}^i\{a_p\}\)。考虑优化。
我们发现，如果我们事先用单调栈预处理每个数前面第一个小于它的位置 \(y\)，那么对于 \(x<y\) 的情况，两者是相同的，可以直接用 \(dp_{y,j}\) 代替（注意 \(y=0\) 除外，因为我们实际上要的是 \(y\) 左边的部分。然后，\(x\ge y\) 的部分没有比 \(a_i\) 更小的，所以就是 \(a_i\sum f_{k,j\oplus 1}\)，直接预处理前缀和即可。
最后统计答案，注意段数的奇偶性不等于关键点的奇偶性，需要重新讨论。
复杂度 \(O(n)\)。
const int P=998244353;
int n,a[200005],s[200005],top,l[200005];
int f[200005][2],sum[200005][2];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
rp(i,n)cin>>a[i];
a[0]=0,s[++top]=0;
rp(i,n){
while(a[i]<=a[s[top]])top--;
l[i]=s[top];
s[++top]=i;
}
f[0][0]=1,f[0][1]=0;
sum[0][0]=1;
rp(i,n)rd(j,2){
f[i][j]=((l[i]==0?0:f[l[i]][j])+1ll*(sum[i-1][j^1]-(l[i]==0?0:sum[l[i]-1][j^1])+P)%P*a[i]%P)%P;
sum[i][j]=(sum[i-1][j]+f[i][j])%P;
}
cout<<(f[n][n&1]-f[n][(n&1)^1]+P)%P<<endl;
return 0;
}
//Crayan_r