cdq分治+摩尔投票

#include<bits/stdc++.h>
using namespace std;
namespace IO{
    char buff[1<<21],*p1=buff,*p2=buff;
    char getch(){
        return p1==p2&&(p2=((p1=buff)+fread(buff,1,1<<21,stdin)),p1==p2)?EOF:*p1++;
    }
    template<typename T>
    void read(T &x){
        char ch=getch();int fl=1;x=0;
        while(ch>'9'||ch<'0'){if(ch=='-')fl=-1;ch=getch();}
        while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getch();}
        x*=fl;
    }
    template<typename T,typename ...Args>
    void read(T &x,Args& ...args){
        read(x);read(args...);
    }
    char obuf[1<<21],*p3=obuf;
    void putch(char ch){
        if(p3-obuf<(1<<21))*p3++=ch;
        else fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=ch;
    }
    char ch[100];
    template<typename T>
    void write(T x){
        if(!x)return putch('0');
        if(x<0)putch('-'),x*=-1;
        int top=0;
        while(x)ch[++top]=x%10+48,x/=10;
        while(top)putch(ch[top]),top--;
    }
    template<typename T,typename ...Args>
    void write(T x,Args ...args){
        write(x),putch(' '),write(args...);
    }
    void flush(){fwrite(obuf,p3-obuf,1,stdout);}
}
using namespace IO;
const int mod=998244353;
inline int Mod(int x){return x>=mod?x-mod:x;}
inline int Inc(int x,int y){return Mod(x+y);}
inline int Sub(int x,int y){return Mod(x+mod-y);}
inline int Mul(int x,int y){return 1ll*x*y%mod;}
inline int inc(int &x,int y){return x=Mod(x+y);}
inline int sub(int &x,int y){return x=Mod(x+mod-y);}
inline int mul(int &x,int y){return x=1ll*x*y%mod;}
inline int poww(int x,int y){
	int sum=1;
	while(y>0){
		if(y&1)mul(sum,x);
		x=1ll*x*x%mod;
		y>>=1;
	}
	return sum;
}
const int N=2e6+5;
int n;
int a[N],w[N];
int f[N];
vector<int>S;
struct node{
	int tree[N<<1];
	inline int lowbit(int x){return x&(-x);}
	inline void add(int x,int y){
		x+=n;
		while(x<=2*n){
			inc(tree[x],y);
			x+=lowbit(x);
		}
	}
	inline int ask(int x){
		x+=n;
		int sum=0;
		while(x){
			inc(sum,tree[x]);
			x-=lowbit(x);
		}
		return sum;
	}
}T[2];
int b[N<<1],maxn;
void sol(int l,int r){
	if(l==r)return;
	int mid=((l+r)>>1);
	sol(l,mid);
	
	for(int i=mid;i>=l;i--){
		b[a[i]]++;
		if(b[a[i]]>b[maxn]){
			if(a[i]!=maxn)S.push_back(a[i]);
			maxn=a[i];
		}
	}
	maxn=0;for(int i=l;i<=mid;i++)b[a[i]]--;
	
	
	for(int i=mid+1;i<=r;i++){
		b[a[i]]++;
		if(b[a[i]]>b[maxn]){
			if(a[i]!=maxn)S.push_back(a[i]);
			maxn=a[i];
		}
	}
	maxn=0;for(int i=mid+1;i<=r;i++)b[a[i]]--;
	
	sort(S.begin(),S.end());
	S.erase(unique(S.begin(),S.end()),S.end());
	
	int res0=0,res1=0;
	for(int i=l;i<=mid;i++)
		if(i&1)inc(res1,f[i]);
		else inc(res0,f[i]);
	for(int i=mid+1;i<=r;i++)
		if(i&1)inc(f[i],res1);
		else inc(f[i],res0);
	for(auto W:S){
		for(int i=l;i<=r;i++)w[i]=(a[i]==W?1:-1);
		for(int i=mid-1;i>=l;i--)w[i]+=w[i+1];
		for(int i=mid+2;i<=r;i++)w[i]+=w[i-1];
		for(int i=l;i<mid;i++)T[i&1].add(-w[i+1],f[i]);T[mid&1].add(0,f[mid]);
		for(int i=mid+1;i<=r;i++)sub(f[i],T[i&1].ask(w[i]-1));
		for(int i=l;i<mid;i++)T[i&1].add(-w[i+1],-f[i]);T[mid&1].add(0,-f[mid]);
	}
	
	S.clear();
	sol(mid+1,r);
}
signed main(){
	f[0]=1;
	read(n);n*=2;
	for(int i=1;i<=n;i++)read(a[i]);
	sol(0,n);
	write(f[n]);
	flush();
	return 0;
}