相当于有 $n$ 个点 $(x_i,y_i)$，求

\[\sum_{s\in2^{[n]} }\left(\max_{i\in s}x_i-\min_{i\in s}x_i\right)\left(\max_{i\in s}y_i-\min_{i\in s}y_i\right)\]

乘法分配率展开

\[\sum_{s\in2^{[n]} }\max_{i\in s}x_i\max_{i\in s}y_i-\sum_{s\in2^{[n]} }\max_{i\in s}x_i\min_{i\in s}y_i-\sum_{s\in2^{[n]} }\min_{i\in s}x_i\max_{i\in s}y_i+\sum_{s\in2^{[n]} }\min_{i\in s}x_i\min_{i\in s}y_i\]

这四个式子做法较为类似，这里以第一个式子（两个 $\max$）为例。

不妨将所有点以 $x_i$ 升序排序，枚举 $i$，这样枚举到的 $x_i$ 便是当前最大的。
插入 $x_i$ 时，当前集合内所有点的 $x$ 坐标均比 $x_i$ 小，需要计算当前集合的所有子集的 $y$ 坐标的 $\max$ 之和，那么集合内第 $i$ 小的数的贡献就是 $2^{i-1}$。
这样会在计算 $x_i$ 的时候把 $x_{i-1}$ 已经计算过的重复计算一遍，差分即可。
可以使用线段树和树状数组来维护集合的所有子集的 $\max$ 之和，插入一个点相当于一个后缀乘 $2$，然后进行一次单点修改。插入新点时，比新点小的数可以用树状数组去计算。

#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=2e5+7,P=998244353;
struct mint{
	int d;
	mint()=default;
	mint(int x):d(x){}
	friend std::istream&operator>>(std::istream&x,mint&y){return x>>y.d;}
	friend std::ostream&operator<<(std::ostream&x,mint y){return x<<y.d;}
	friend mint operator+(mint x,mint y){return (x.d+=y.d)<P?x.d:x.d-P;}
	mint&operator+=(mint z){return (d+=z.d)<P?d:d-=P,*this;}
	friend mint operator-(mint x,mint y){return (x.d-=y.d)<0?x.d+P:x.d;}
	mint&operator-=(mint z){return (d-=z.d)<0?d+=P:d,*this;}
	friend mint operator*(mint x,mint y){return int(1ll*x.d*y.d%P);}
	mint&operator*=(mint z){return d=int(1ll*d*z.d%P),*this;}
	static mint qpow(int x,int y=P-2){int z=1;for(;y;y>>=1,x=int(1ll*x*x%P))if(y&1)z=int(1ll*x*z%P);return z;}
	friend mint operator/(mint x,mint y){return x*=qpow(y.d);}
	mint&operator/=(mint z){return (*this)*=qpow(z.d);}
	friend mint operator^(mint x,mint y){return qpow(x.d,y.d);}
	mint&operator^=(mint z){return *this=qpow(d,z.d);}
	mint operator()(mint z)const{return qpow(d,z.d);}
	mint&operator[](mint z){return *this=qpow(d,z.d);}
	mint inv()const{return qpow(d);}
	mint pow(mint z)const{return qpow(d,z.d);}
	int operator+()const{return d;}
	mint operator-()const{return d?P-d:0;}
	int operator~()const{return ~d;}
};
mint operator""_m(lolu x){return mint(int(x%P));}
int n;
pii a[N];
mint pw[N];
mint sum[N<<2],tag1[N<<2],tag2[N<<2],len[N<<2];
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)>>1)
void build(int u,int l,int r){
	sum[u]=0;
	tag1[u]=0;
	tag2[u]=1;
	len[u]=r-l+1;
	if(l==r)return;
	build(ls,l,mid);build(rs,mid+1,r);
}
void pushdw(int u){
	tag1[ls]=tag1[ls]*tag2[u]+tag1[u];
	tag2[ls]*=tag2[u];
	sum[ls]=sum[ls]*tag2[u]+tag1[u]*len[ls];
	tag1[rs]=tag1[rs]*tag2[u]+tag1[u];
	tag2[rs]*=tag2[u];
	sum[rs]=sum[rs]*tag2[u]+tag1[u]*len[rs];
	tag1[u]=0;tag2[u]=1;
}
void upd1(int u,int l,int r,int x,int y,mint k){
	if(x<=l&&r<=y){
		tag1[u]+=k;
		sum[u]+=k*len[u];
		return;
	}
	pushdw(u);
	if(x<=mid)upd1(ls,l,mid,x,y,k);
	if(y>mid)upd1(rs,mid+1,r,x,y,k);
	sum[u]=sum[ls]+sum[rs];
}
void upd2(int u,int l,int r,int x,int y,mint k){
	if(x<=l&&r<=y){
		tag1[u]*=k;
		tag2[u]*=k;
		sum[u]*=k;
		return;
	}
	pushdw(u);
	if(x<=mid)upd2(ls,l,mid,x,y,k);
	if(y>mid)upd2(rs,mid+1,r,x,y,k);
	sum[u]=sum[ls]+sum[rs];
}
int d[N];
void cls(){
	for(int i=1;i<=n;i++)
		d[i]=0;
}
void add(int x,int y){
	for(;x<=n;x+=x&-x)
		d[x]+=y;
}
int ask1(int x){
	int y=0;
	for(;x;x-=x&-x)
		y+=d[x];
	return y;
}
int ask2(int x){
	return ask1(n)-ask1(x-1);
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(nullptr);
	cin>>n;
	pw[0]=1;
	for(int i=1;i<=n;i++){
		a[i].fi=i;
		cin>>a[i].se;
		pw[i]=pw[i-1]+pw[i-1];
	}
	mint ans=0;
	// max max
	build(1,1,n);cls();
	sort(a+1,a+1+n,[](pii x,pii y){
		return x.fi<y.fi;
	});
	for(int i=1;i<=n;i++){
		mint tmp=sum[1];
		upd2(1,1,n,a[i].se,n,2);
		upd1(1,1,n,a[i].se,a[i].se,pw[ask1(a[i].se)]*a[i].se);
		add(a[i].se,1);
		ans+=a[i].fi*(sum[1]-tmp);
	}
	// max min
	build(1,1,n);cls();
	sort(a+1,a+1+n,[](pii x,pii y){
		return x.fi<y.fi;
	});
	for(int i=1;i<=n;i++){
		mint tmp=sum[1];
		upd2(1,1,n,1,a[i].se,2);
		upd1(1,1,n,a[i].se,a[i].se,pw[ask2(a[i].se)]*a[i].se);
		add(a[i].se,1);
		ans-=a[i].fi*(sum[1]-tmp);
	}
	// min max
	build(1,1,n);cls();
	sort(a+1,a+1+n,[](pii x,pii y){
		return x.fi>y.fi;
	});
	for(int i=1;i<=n;i++){
		mint tmp=sum[1];
		upd2(1,1,n,a[i].se,n,2);
		upd1(1,1,n,a[i].se,a[i].se,pw[ask1(a[i].se)]*a[i].se);
		add(a[i].se,1);
		ans-=a[i].fi*(sum[1]-tmp);
	}
	// min min
	build(1,1,n);cls();
	sort(a+1,a+1+n,[](pii x,pii y){
		return x.fi>y.fi;
	});
	for(int i=1;i<=n;i++){
		mint tmp=sum[1];
		upd2(1,1,n,1,a[i].se,2);
		upd1(1,1,n,a[i].se,a[i].se,pw[ask2(a[i].se)]*a[i].se);
		add(a[i].se,1);
		ans+=a[i].fi*(sum[1]-tmp);
	}
	cout<<ans;
	return 0;
}