这也太帅了。
对于这类每种元素有多种选择，但结果可能相同的。可以考虑钦定一个策略构造结果与元素序列的双射。
每个人能看作一个区间，考虑策略 “若在左端点签名与右端点签名产生的最终名单不同，则钦定在左端点签名”。
当且仅当没有其他人在区间 \([A_i,B_i]\) 中签名才会满足该决策条件。因为这个条件会影响后面人的决策，有后效性，所以不好 dp。
所以考虑容斥掉不符合该决策的可能数量。枚举不合法区间集合，每个不合法区间相当于固定了所有左端点/右端点被包含在其中的区间的选法（只能在另一端留下签名）。剩下的 \(c\) 个区间没有限制，选法有 \(2^c\)。
需要注意的是不合法区间之间不交，否则必定存在区间无法选择左端点，就不可能违背该策略。
考虑如何枚举不合法区间集合。考虑直接在 dp 过程中把所有情况区间 \(i\) 对 \(ans\) 的贡献计算。
\(f_i\) 表示前 \(i\) 个区间对 \(ans\) 的贡献，则第 \(i\) 个区间对答案的转移有：
- 在不合法集合中：
\[f_{r}=-f_{l-1}
\]
其中区间 \(i\) 不合法固定了 \([l,r]\) 中区间的选择，不合法集合中多了一个元素所以需要额外的 \(-1\)。
- 不在不合法集合中：
\[f_i=2f_{i-1}
\]
表示选左端点或右端点。
而 \([l,r]\) 是可以双指针求得，dp 也是 \(O(n)\)，所以总复杂度 \(O(n)\)。
Takanashi Rikka
// Problem: AT_agc061_c [AGC061C] First Come First Serve
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_agc061_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define fin(x) freopen(#x".in","r",stdin)
#define fout(x) freopen(#x".out","w",stdout)
#define fr(x) fin(x),fout(x);
#define Fr(x,y) fin(x),fout(y)
#define INPUT(_1,_2,FILE,...) FILE
#define IO(...) INPUT(__VA_ARGS__,Fr,fr)(__VA_ARGS__)
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define intz(x,z) memset((x),(z),sizeof((x)))
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
inline ll lowbit(ll x){return x&-x;}
#define fi first
#define se second
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
inline void cmx(auto &x,ll y){if(y>x)x=y;}
inline void cmn(auto &x,ll y){if(y<x)x=y;}
const int N=5e5+5,mod=998244353;
// #define int ll
int f[N],l[N],r[N];
void UesugiErii(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>l[i]>>r[i];f[0]=1;for(int i=1,R=0,L=0;i<=n;i++){while(R<=n&&l[R]<=r[i])++R;--R;while(L<=n&&r[L]<=l[i])++L;--L;f[i]=(f[i]+1ll*f[i-1]*2%mod)%mod,f[R]=(f[R]+mod-f[L])%mod;}cout<<f[n];
}
signed main(){//cfast;int _=1;//cin>>_;for(;_;_--)UesugiErii();return 0;
}