依题意得，当确定了两个端点后，中间的可选可不选，考虑枚举左端点，找比它大的右端点，求方案数，时间复杂度\(O(n^2)\)，显然会T
考虑优化，若两个端点分别是i,j，则方案数为\(2^{j-i-1}=2^j\div 2^{i+1}\)，所以考虑权值线段树记录\(2^j\)，倒序枚举左端点即可
代码：
#include<cstdio>
#define ll long long
using namespace std;
const int p=1e9,mod=998244353;
int n,a[300005];
int ls[5000005],rs[5000005],idx,rt;
ll val[5000005];
ll qpow(ll x,int y)
{
ll res=1;
while(y)
{
if(y&1) res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
int add(int id,int l,int r,int x,int v)
{
if(!id) id=++idx;
if(l==r)
{
val[id]=(qpow(2,v)+val[id])%mod;
return id;
}
int mid=(l+r)>>1;
if(x<=mid) ls[id]=add(ls[id],l,mid,x,v);
else rs[id]=add(rs[id],mid+1,r,x,v);
val[id]=(val[ls[id]]+val[rs[id]])%mod;
return id;
}
ll query_val(int id,int l,int r,int ql,int qr)
{
if(!id||l>qr||r<ql) return 0;
if(l>=ql&&r<=qr)
{
return val[id];
}
int mid=(l+r)>>1;
ll res=0;
if(mid>=ql) res=query_val(ls[id],l,mid,ql,qr);
if(mid<qr) res=(res+query_val(rs[id],mid+1,r,ql,qr))%mod;
return res%mod;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
ll ans=0;
for(int i=n;i>0;i--)
{
ll cnt=query_val(rt,1,p,a[i],p);
// printf("%d ",cnt);
ans=(ans+cnt*qpow(qpow(2,i+1),mod-2)%mod)%mod;
rt=add(rt,1,p,a[i],i);
}
printf("%lld",ans%mod);
return 0;
}