To denote problems, I will use quotes to denote the number of problems proposed for that postion so far (e.g. A' represents the first A proposed for the round, A'' represents second A proposed, etc). If the problem is in the final set, then it will be bolded. For dates, I will use the american standard notation (mm/dd).

Also, I will not go in detail about why problems were rejected/unused because they might appear in the future.

8/11: Codeforces Round 965 (Div. 2) has just concluded and sum has shipped himself off to college and won't have time due to attending frat parties his studies. I invite Proof_by_QED to problemset with me. We decide to get cooking straight away.

8/12: Proof_by_QED proposes D'. Gets accepted.

8/13: Proof_by_QED proposes E'. Problem accepted for backup.

8/14: Proof_by_QED proposes D''. Problem accepted for backup.

8/19: Proof_by_QED proposes E'', F' and G'. Both gets accepted for main set at the time. Seriously, bro just became the new BledDest.

8/21: We got bored and decided to focus on Codeforces Round 971 (Div. 4). Due to difficulty issues, we transfered problem E from that contest to problem B1 and B2 for this contest. B2 ultimately became D :)

8/22: Proof_by_QED proposes B', but satyam343 buffs it into F instead. Somewhere along the lines I also came up with A' and B'', both getting initially accepted.

8/23: Round gets put up for testing with 7 problems.

8/25: I came up with an idea for D'''. Also, Proof_by_QED proposes C, but initially gets ignored lmao.

8/26: satyam343 modifies B'' into D''''. Later, I also propose E''''.

8/28: satyam343 tries to modifies B'' again into C''. sum wakes up from his slumber and proposes F''.

8/29: I propose A''.

8/31: Proof_by_QED proposes D''''' and gets accepted.

9/2: satyam343 buffs D''' and it became NOTEQUALTREE.

9/6: Proof_by_QED and satyam343 modifies D' and it becomes G (G1). Later, A_G solved it in subquadratic, and it became G2.

9/9: I modify B'' into D''''''.

9/11: satyam343 modifies B'' into D'''''''. We hold a poll in our testing server to choose the victor among D'''''' and D'''''''.

9/12: I invent and propose C''', but wasn't accepted. satyam343 modifies B'' into D'''''''', but unused due to difficulty issues.

9/14: I invent and propose D''''''''', which was unused due to difficulty issues. Later that night, the aforementioned poll concludes, crowning D'''''' with 7 votes to 2. However, both candidates had difficulty issues so we still decided against using any of them (essentially we polled for nothing).

9/15: Proof_by_QED proposes B'''' and gets initially accepted, however, was later rejected.

9/17: I propose A''' but it wasn't great.

9/20: Proof_by_QED brings C up again and it gets prepared.

9/23: satyam343 modifies B'' into D'''''''''', but as the original author of B'', I didn't like it.

9/24: satyam343 modifies D''''''''' into D''''''''''', and it gets prepared.

9/28: Proof_by_QED modifies a unused problem I proposed for Codeforces Round 965 (Div. 2) into A'''', but unused due to difficulty issues.

9/30: Proof_by_QED proposes and prepares B. Later that night, satyam343 has conflicting thoughts whether to replace D''''''''''' yet again, but I held him at gunpoint to accept the problem spent 30 minutes convincing him that it is a good problem. This problem became E. For those of you who enjoyed the problem, you're welcome lmao.

10/02 — 10/17: Final testing and preparation.

10/13: Proof_by_QED proposes current A.

First, what is the maximum possible value of $$$c_i-b_j$$$ for any $$$i,j$$$? Since $$$c_i$$$ is the maximum element of some subset of $$$a$$$ and $$$b_i$$$ is the minimum element of some subset of $$$a$$$, the maximum possible value of $$$c_i-b_j$$$ is $$$max(a)-min(a)$$$.

Also note that $$$c_1=b_1$$$ for any reordering of $$$a$$$. By reordering such that the largest element of $$$a$$$ appears first and the smallest element of $$$a$$$ appears second, the maximum possible value of the score is achieved. This results in a score of $$$(max(a)-min(a))\cdot(n-1)$$$.

for i in range(int(input())):
    n = int(input())
    mx = 0
    mn= 1000000
    lst = input().split()
    for j in range(n):
        x = int(lst[j])
        mx = max(mx, x)
        mn = min(mn, x)
    print((mx-mn)*(n-1))

Observation: $$$f(t)-g(t)$$$ is odd.

Proof: $$$f(t)+g(t)$$$ is the set of all non-empty subsets of $$$t$$$, which is $$$2^{|t|}-1$$$, which is odd. The sum and difference of two integers has the same parity, so $$$f(t)-g(t)$$$ is always odd.

By including exactly one $$$1$$$ in the string $$$s$$$, we can make $$$f(s)=2^{n-1}-1$$$ and $$$g(s)=2^{n-1}$$$, or $$$f(s)-g(s)=1$$$ by the multiplication principle. Clearly, this is the best we can do. So, we print out any string with exactly one $$$1$$$.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        cout << '1';
        for(int i = 1; i < n; i++) cout << '0';
        cout << endl;
    }
}

Let's understand what Alice wants to do. She wants to separate a statement that evaluates to true between two or's. This guarantees her victory since or is evaluated after all and's.

First, if the first or last boolean is true, then Alice instantly wins by placing or between the first and second, or second to last and last booleans.

Otherwise, if there are two true's consecutively, Alice can also win. Alice may place or before the first of the two on her first move. If Bob does not put his operator between the two true's, then Alice will put an or between the two true's on her next move and win. Otherwise, Bob does place his operator between the two true's. However, no matter what Bob placed, the two true's will always evaluate to true, so on her second move Alice can just place an or on the other side of the two true's to win.

We claim these are the only two cases where Alice wins. This is because otherwise, there does not contain two true's consecutively. Now, whenever Alice places an or adjacent to a true, Bob will respond by placing and after the true, which will invalidate this clause to be false.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        vector<int> v(n);
        for(int i = 0; i < n; i++) {
            if(s[i]=='1') v[i]=1;
        }
        bool win = false;
        if(v[0]||v[n-1]) win=true;
        for(int i = 1; i < n; i++) {
            if(v[i]&&v[i-1]) win=true;
        }
        if(win) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

Observation: Through a series of swaps, we can swap an element from position $$$i$$$ to position $$$j$$$ (WLOG, assume $$$i \lt j$$$) if there is no such $$$k$$$ such that $$$i \leq k \lt j$$$ such that $$$s_k = \texttt{L}$$$ and $$$s_{k+1} = \texttt{R}$$$.

Let's mark all indices $$$i$$$ such that $$$s_i = \texttt{L}$$$ and $$$s_{i+1} = \texttt{R}$$$ as bad. If $$$pos_i$$$ represents the position of $$$i$$$ in $$$p$$$, then we must make sure it is possible to swap from $$$\min(i, pos_i)$$$ to $$$\max(i, pos_i)$$$. As you can see, we can model these conditions as intervals. We must make sure there are no bad indices included in any intervals.

We need to gather indices $$$i$$$ such that $$$i$$$ is included in at least one interval. This can be done with difference array. Let $$$d_i$$$ denote the number of intervals that include $$$i$$$. If $$$d_i \gt 0$$$, then we need to make sure $$$i$$$ is not a bad index.

We can keep all bad indices in a set. Notice that when we update $$$i$$$, we can only potentially toggle indices $$$i$$$ and $$$i-1$$$ from good to bad (or vice versa). For example, if $$$s_i = \texttt{L}$$$, $$$s_i = \texttt{R}$$$, $$$d_i \gt 0$$$ and index $$$i$$$ is not in the bad set, then we will insert it. After each query, if the bad set is empty, then the answer is "YES".

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n,q;
        cin >> n >> q;
        vector<int> perm(n);
        for(int i = 0; i < n; i++) cin >> perm[i];
        for(int i = 0; i < n; i++) perm[i]--;
        vector<int> invperm(n);
        for(int i = 0; i < n; i++) invperm[perm[i]]=i;
        vector<int> diffArr(n);
        for(int i = 0; i < n; i++) {
            diffArr[min(i, invperm[i])]++;
            diffArr[max(i, invperm[i])]--;
        }
        for(int i = 1; i < n; i++) diffArr[i]+=diffArr[i-1];
        string s;
        cin >> s;
        set<int> problems;
        for(int i = 0; i < n-1; i++) {
            if(s[i]=='L'&&s[i+1]=='R'&&diffArr[i]!=0) {
                problems.insert(i);
            } 
        }
        while(q--) {
            int x;
            cin >> x;
            x--;
            if(s[x]=='L') {
                s[x]='R';
            } else {
                s[x]='L';
            }
            if(s[x-1]=='L'&&s[x]=='R'&&diffArr[x-1]!=0) {
                problems.insert(x-1);
            } else {
                problems.erase(x-1);
            }
            if(s[x]=='L'&&s[x+1]=='R'&&diffArr[x]!=0) {
                problems.insert(x);
            } else {
                problems.erase(x);
            }
            if(problems.size()) {
                cout << "NO" << endl;
            } else {
                cout << "YES" << endl;
            }
        }
    }
}

Observation: The score of $$$b$$$ is equivalent to $$$f_0$$$ + $$$\min(f_0, f_1)$$$ + $$$\ldots$$$ + $$$\min(f_0, \ldots, f_{n-1})$$$ where $$$f_i$$$ stores the frequency of integer $$$i$$$ in $$$b$$$.

Intuition: We can greedily construct the $$$k$$$ arrays by repeating this step: Select the minimum $$$j$$$ such that $$$f_j = 0$$$ and $$$\min(f_0, \ldots f_{j-1}) \gt 0$$$, and construct the array $$$[0, 1, \ldots, j-1]$$$. This is optimal because every element we add will increase the MEX by $$$1$$$, which will increase the score by $$$1$$$. If we add $$$j$$$, the MEX will not increase. Also, when we add an element, we cannot increase the score by more than $$$1$$$. Adding less than $$$j$$$ elements cannot increase MEX for future arrays.

From this observation, we can see that only the frequency array of $$$a$$$ matters. From now on, let's denote the frequency of $$$i$$$ in $$$a$$$ as $$$f_i$$$. We can find the sum over all subsequences using dynamic programming.

Let's denote $$$dp[i][j]$$$ as the number of subsequences containing only the first $$$i$$$ integers and $$$min(f_0, \ldots, f_i) = j$$$. Initially, $$$dp[0][i] = \binom{f_0}{i}$$$. To transition, we need to consider two cases:

In the first case, let's assume $$$j \lt \min(f_0, \ldots, f_{i-1})$$$. The number of subsequences that can be created is $$$(\sum_{k=j+1}^n dp[i-1][k]) \cdot \binom{f_i}{j}$$$. That is, all the subsequences from previous length such that it is possible for $$$j$$$ to be the new minimum, multiplied by the number of subsequences where $$$f_i = j$$$.

In the second case, let's assume $$$j \geq \min(f_0, \ldots, f_{i-1})$$$. The number of subsequences that can be created is $$$(\sum_{k=j}^{f_i} \binom{f_i}{k}) \cdot dp[i-1][j]$$$. That is, all subsequences containing at least $$$j$$$ elements of $$$i$$$, multiplied by all previous subsequences with minimum already equal to $$$j$$$.

The total score is $$$dp[i][j] \cdot j \cdot 2^{f_{i+1} + \dots + f_{n-1}}$$$ over the length of the prefix $$$i$$$ and prefix minimum $$$j$$$.

We can speed up the calculations for both cases using suffix sums, however, this still yields an $$$O(n^2)$$$ algorithm. However, $$$j$$$ is bounded to the interval $$$[1, f_i]$$$ for each $$$i$$$. Since the sum of $$$f_i$$$ is $$$n$$$, the total number of secondary states is $$$n$$$. This becomes just a constant factor, so the total complexity is $$$O(n)$$$.

#include <bits/stdc++.h>
#define int long long
#define ll long long 
#define pii pair<int,int> 
#define piii pair<pii,pii>
#define fi first
#define se second
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

const int MX = 2e5;
ll fact[MX+1];
ll ifact[MX+1];
ll MOD=998244353;
 
ll binPow(ll base, ll exp) {
    ll ans = 1;
    while(exp) {
        if(exp%2) {
            ans = (ans*base)%MOD;
        }
        base = (base*base)%MOD;
        exp /= 2;
    }
    return ans;
}
 
int nCk(int N, int K) {
    if(K>N||K<0) {
        return 0;
    }
    return (fact[N]*((ifact[K]*ifact[N-K])%MOD))%MOD;
}
 
void ICombo() {
	fact[0] = 1;
    for(int i=1;i<=MX;i++) {
        fact[i] = (fact[i-1]*i)%MOD;
    }    
    ifact[MX] = binPow(fact[MX],MOD-2);
    for(int i=MX-1;i>=0;i--) {
        ifact[i] = (ifact[i+1]*(i+1))%MOD;
    }
}

void solve() {
    int n, ans=0; cin >> n;
    vector<int> c(n);
    for (int r:c) {
        cin >> r; c[r]++; 
    }
    vector<vector<int>> dp(n,vector<int>(1));
    vector<int> ps, co; 
    for (int i = 1; i <= c[0]; i++) dp[0].push_back(nCk(c[0],i));
    for (int i = 1; i < n; i++) {
        ps.resize(1); co=ps; 
        for (int r:dp[i-1]) ps.push_back((ps.back()+r)%MOD); 
        int m=ps.size()-1;
        dp[i].resize(min(m,c[i]+1));
        for (int j = 0; j <= c[i]; j++) co.push_back((co.back()+nCk(c[i],j))%MOD);
        for (int j = 1; j < dp[i].size(); j++) dp[i][j]=nCk(c[i],j)*(ps[m]-ps[j]+MOD)%MOD+(co.back()-co[j+1]+MOD)*dp[i-1][j]%MOD; 
    }
    int j=0;
    for (auto r:dp) {
        n-=c[j++];
        for (int i = 1; i < r.size(); i++) (ans+=i*r[i]%MOD*binPow(2,n))%=MOD;
    }
    cout << ans << "\n"; 
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
        ICombo();
	int t = 1; cin >> t;
	while (t--) solve();
}

First, let's try to find whether a single array is orangutan-approved or not.

Claim: The array $$$b$$$ of size $$$n$$$ is not orangutan-approved if and only if there exists indices $$$1\leq w \lt x \lt y \lt z \leq n$$$ such that $$$b_w=b_y$$$, $$$b_x=b_z$$$, and $$$b_w\neq b_x$$$.

Proof: Let's prove this with strong induction. For $$$n=0$$$, the claim is true because the empty array is orangutan-approved. Now, let's suppose that the claim is true for all $$$m \lt n$$$.

Now, let $$$s$$$ be a sorted sequence such that $$$x$$$ is in $$$s$$$ if and only if $$$b_x=b_1$$$. Suppose $$$s$$$ is length $$$k$$$. We can split the array $$$b$$$ into disjoint subarrays $$$c_1, c_2, \ldots, c_k$$$ such that $$$c_i$$$ is the subarray $$$b[s_i+1\ldots s_{i+1}-1]$$$ for all $$$1 \leq i \lt k$$$ and $$$c_k=b[s_k+1\ldots n]$$$ That is, $$$c_i$$$ is the subarray that lies between each occurrence of $$$b_1$$$ in the array $$$b$$$.

First, we note that the set of unique elements of $$$c_i$$$ and $$$c_j$$$ cannot contain any elements in common for all $$$i\neq j$$$. This is because suppose that there exists $$$i$$$ and $$$j$$$ such that $$$i \lt j$$$ and the set of unique values in $$$c_i$$$ and $$$c_j$$$ both contain $$$y$$$. Then, in the original array $$$b$$$, there must exist a subsequence $$$b_1, y, b_1, y$$$. This makes our premise false.

By our inductive claim, each of the arrays $$$c_1, c_2, \ldots, c_k$$$ must be orangutan-approved. Since there are no overlapping elements, we may delete each of the arrays $$$c_1, c_2, \ldots, c_k$$$ separately. Finally, the array $$$b$$$ is left with $$$k$$$ copies of $$$b_1$$$, and we can use one operation to delete all remaining elements in the array $$$b$$$.

Now, how do we solve for all queries? First, precompute the array $$$last$$$, which is the array containing for each $$$i$$$ the largest index $$$j \lt i$$$ such that $$$a[j]=a[i]$$$. Let's then use two pointers to compute the last element $$$j \lt i$$$ such that $$$a[j\ldots i]$$$ is orangutan-approved but $$$a[j-1\ldots i]$$$ is not, and store this in an array called $$$left$$$. Let's also keep a maximum segment tree $$$next$$$ such that $$$next[i]$$$ is the first element $$$j \gt i$$$ such that $$$a_j=a_i$$$. As we sweep from $$$i-1$$$ to $$$i$$$, we do the following:

1. Set $$$L=left[i-1]$$$

2. Otherwise, while $$$\max(next[L...last[i]-1] \gt last[i]$$$ and $$$last[i]\neq-1$$$), increment $$$L$$$ by $$$1$$$.

3. Set $$$left[i]=L$$$

When the $$$left$$$ array is fully calculated, we can solve each query in $$$O(1)$$$.

#pragma GCC optimize("Ofast")
 
#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define nline "\n"
#define f first
#define s second
#define sz(x) x.size()
#define all(x) x.begin(),x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll INF_ADD=1e18;
const ll MOD=1e9+7;
const ll MAX=1048579;
class ST {
public:
    vector<ll> segs;
    ll size = 0;
    ll ID = 0;
 
    ST(ll sz) {
        segs.assign(2 * sz, ID);
        size = sz;  
    }   
   
    ll comb(ll a, ll b) {
        return max(a, b);  
    }
 
    void upd(ll idx, ll val) {
        segs[idx += size] = val;
        for(idx /= 2; idx; idx /= 2) segs[idx] = comb(segs[2 * idx], segs[2 * idx + 1]);
    }
 
    ll query(ll l, ll r) {
        ll lans = ID, rans = ID;
        for(l += size, r += size + 1; l < r; l /= 2, r /= 2) {
            if(l & 1) lans = comb(lans, segs[l++]);
            if(r & 1) rans = comb(segs[--r], rans);
        }
        return comb(lans, rans);
    }
}; 
void solve(){
  ll n,q,l=1; cin>>n>>q;
  ST track(n+5);
  vector<ll> a(n+5),last(n+5,0),lft(n+5);
  for(ll i=1;i<=n;i++){
    cin>>a[i];
    ll till=last[a[i]];
    while(track.query(l,till)>=till+1){
      l++;
    }
    if(till){
      track.upd(till,i);
    }
    lft[i]=l;
    last[a[i]]=i;
  }
  while(q--) {
    ll l,r; cin>>l>>r;
    if(lft[r]<=l){
      cout<<"YES\n";
    } 
    else{
      cout<<"NO\n";
    }
  }
}
int main()                                                                                 
{         
  ios_base::sync_with_stdio(false);                         
  cin.tie(NULL);                                  
  ll test_cases=1;                 
  cin>>test_cases;
  while(test_cases--){
    solve();
  }
} 

To find the score of a set of intervals $$$([l_1, r_1], [l_2, r_2], \ldots, [l_v, r_v])$$$, we follow these steps:

Initially, the score is set to $$$0$$$.

We perform the following process repeatedly:

• Let $$$x$$$ be the interval with the smallest $$$r_i$$$ among all active intervals.
• Let $$$y$$$ be the interval with the largest $$$l_i$$$ among all active intervals.
• If $$$r_x \lt l_y$$$, add $$$l_y - r_x$$$ to the score, mark intervals $$$x$$$ and $$$y$$$ as inactive, and continue the process.
• If $$$r_x \geq l_y$$$, stop the process.

At the end of this process, all active intervals will intersect at least one common point.

Now, we need to prove that the process indeed gives us the minimum possible score. We can prove this by induction.

Let $$$S$$$ be some set of intervals, and let $$$x$$$ and $$$y$$$ be the intervals defined above. Consider the set $$$S' = S \setminus {x, y}$$$ (i.e., $$$S'$$$ is the set $$$S$$$ excluding $$$x$$$ and $$$y$$$). We claim that:

This is true because, for $$$x$$$ and $$$y$$$ to intersect, we must perform at least $$$\text{distance}(x, y)$$$ operations. Our construction achieves the lower bound of $$$\text{score}(S') + \text{distance}(x, y)$$$. Thus,

During the process, we pair some intervals (possibly none). Specifically, in the $$$k$$$-th step, we pair the interval with the $$$k$$$-th smallest $$$r_i$$$ with the interval having the $$$k$$$-th largest $$$l_j$$$, and add the distance between them to the score.

In the problem G1, we can compute the contribution of each pair of intervals as follows:

Suppose we consider a pair $$$(i, j)$$$. Without loss of generality, assume that $$$r_i \lt l_j$$$.

The pair $$$(i, j)$$$ will be considered in some subset $$$S$$$ if there are exactly $$$x$$$ intervals $$$p$$$ such that $$$r_p \lt r_i$$$ and exactly $$$x$$$ intervals $$$p$$$ such that $$$l_p \gt l_j$$$, for some non-negative integer $$$x$$$.

Let there be $$$g$$$ intervals $$$p$$$ such that $$$r_p \lt r_i$$$ and $$$h$$$ intervals $$$p$$$ such that $$$l_p \gt l_j$$$.

For $$$(i, j)$$$ to be paired in some subset $$$S$$$, we must choose $$$x$$$ intervals from the $$$g$$$ intervals on the left and $$$x$$$ intervals from the $$$h$$$ intervals on the right, for some non-negative integer $$$x$$$. There are no restrictions on the remaining $$$n - 2 - g - h$$$ intervals.

Therefore, the contribution of $$$(i, j)$$$ is:

We can simplify this sum using the identity:

(This is a form of the Vandermonde Identity.)

Thus, the contribution of $$$(i, j)$$$ becomes:

This can be computed in $$$O(1)$$$ time.

Note that in the explanation above, we assumed that the interval endpoints are distinct for simplicity. If they are not, we can order the intervals based on their $$$l_i$$$ values to maintain consistency.

Let us find the contribution of $$$r[i]$$$, the right endpoint of $$$i$$$-th interval.

Let $$$x$$$ be the number of intervals $$$j$$$ such that $$$r[j] \lt r[i]$$$, and let $$$y$$$ be the number of intervals $$$j$$$ such that $$$l[j] \gt r[i]$$$.

To determine the contribution of $$$r[i]$$$ to the final answer, we consider selecting $$$p$$$ intervals from the $$$x$$$ intervals to the left and $$$q$$$ intervals from the $$$y$$$ intervals to the right, with the constraint that $$$p \lt q$$$. We require $$$p \lt q$$$ so that interval $$$i$$$ is paired with some other interval on the right (as discussed in the solution for G1). Therefore, the contribution of $$$r[i]$$$ can be expressed as:

Here, $$$\text{ways}(x, y)$$$ represents the number of valid selections where $$$p \lt q$$$.

Calculating $$$\text{ways}(x, y)$$$

To compute $$$\text{ways}(x, y)$$$, we can use the Vandermonde identity to simplify the expression:

This can be rewritten as:

Define the function $$$g(k)$$$ as:

By applying the Vandermonde identity, we get:

Thus, the total number of ways is:

We can simplify this summation using the property of binomial coefficients:

where the function $$$h(p, q)$$$ is defined as:

Efficient Computation of $$$h(p, q)$$$

Note that:

Suppose throughout the solution, we call the function $$$h(p, q)$$$ $$$d$$$ times for pairs $$$(p_1, q_1), (p_2, q_2), \ldots, (p_d, q_d)$$$, in that order. We can observe that:

Since $$$h(p_i, q_i)$$$ can be computed from $$$h(p_{i-1}, q_{i-1})$$$ in $$$|p_i - p_{i-1}| + |q_i - q_{i-1}|$$$ operations, the amortized time complexity for this part is $$$O(n)$$$.

Final Contribution

Combining the above results, the contribution of $$$r[i]$$$ to the answer is:

A similar calculation can be applied to the contribution of $$$l[i]$$$. By summing these contributions across all relevant intervals, we obtain the final answer.

#pragma GCC optimize("Ofast")
 
#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;   
using namespace std;
#define ll long long
#define ld long double
#define nline "\n"
#define f first
#define s second
#define sz(x) (ll)x.size()
#define vl vector<ll>
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;
#define all(x) x.begin(),x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------     
const ll MOD=998244353;
const ll MAX=500500;
vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1);
ll binpow(ll a,ll b,ll MOD){
    ll ans=1;
    a%=MOD;  
    while(b){
        if(b&1)
            ans=(ans*a)%MOD;
        b/=2;
        a=(a*a)%MOD;
    }
    return ans;
}
ll inverse(ll a,ll MOD){
    return binpow(a,MOD-2,MOD);
} 
void precompute(ll MOD){
    for(ll i=2;i<MAX;i++){
        fact[i]=(fact[i-1]*i)%MOD;
    }
    inv_fact[MAX-1]=inverse(fact[MAX-1],MOD);
    for(ll i=MAX-2;i>=0;i--){
        inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD;
    }
}
ll nCr(ll a,ll b,ll MOD){
    if((a<0)||(a<b)||(b<0))
        return 0;   
    ll denom=(inv_fact[b]*inv_fact[a-b])%MOD;
    return (denom*fact[a])%MOD;  
}
ll l[MAX],r[MAX],lft[MAX],rght[MAX],power[MAX];
void solve(){ 
  ll n; cin>>n;
  power[0]=1;
  for(ll i=1;i<=n;i++){
    cin>>l[i]>>r[i];
    power[i]=(power[i-1]*2ll)%MOD;
  }
  for(ll i=1;i<=n;i++){
    lft[i]=rght[i]=0;
    for(ll j=1;j<=n;j++){
      if(make_pair(r[i],i)>make_pair(r[j],j)){
        lft[i]++;
      }
      if(make_pair(l[i],i)<make_pair(l[j],j)){
        rght[i]++;
      }
    }
  }
  ll ans=0;
  for(ll i=1;i<=n;i++){
    for(ll j=1;j<=n;j++){
      if(r[i]<l[j]){
        ll found=lft[i]+rght[j];
        ll now=nCr(found,lft[i],MOD)*(l[j]-r[i]);
        now%=MOD;
        ll remaining=n-found-2;
        ans=(ans+now*power[remaining])%MOD;
      }
    }
  }
  cout<<ans<<nline;
  return;    
}  
int main()                                                                                 
{         
  ios_base::sync_with_stdio(false);                         
  cin.tie(NULL);                              
  ll test_cases=1;                 
  cin>>test_cases;
  precompute(MOD);
  while(test_cases--){
    solve();
  }
  cout<<fixed<<setprecision(12);  
  cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
} 

#pragma GCC optimize("Ofast")
 
#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;   
using namespace std;
#define ll long long
#define ld long double
#define nline "\n"
#define f first
#define s second
#define sz(x) (ll)x.size()
#define vl vector<ll>
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;
#define all(x) x.begin(),x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------     
const ll MOD=998244353;
const ll MAX=5000500;
vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1);
ll binpow(ll a,ll b,ll MOD){
    ll ans=1;
    a%=MOD;  
    while(b){
        if(b&1)
            ans=(ans*a)%MOD;
        b/=2;
        a=(a*a)%MOD;
    }
    return ans;
}
ll inverse(ll a,ll MOD){
    return binpow(a,MOD-2,MOD);
} 
void precompute(ll MOD){
    for(ll i=2;i<MAX;i++){
        fact[i]=(fact[i-1]*i)%MOD;
    }
    inv_fact[MAX-1]=inverse(fact[MAX-1],MOD);
    for(ll i=MAX-2;i>=0;i--){
        inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD;
    }
}
ll nCr(ll a,ll b,ll MOD){
    if((a<0)||(a<b)||(b<0))
        return 0;   
    ll denom=(inv_fact[b]*inv_fact[a-b])%MOD;
    return (denom*fact[a])%MOD;  
}
ll l[MAX],r[MAX],power[MAX];
ll ans=0,on_left=0,on_right,len;
ll x=0,y=0,ways=0,inv2;
ll getv(){
  while(x>=len+1){
    ways=((ways+nCr(x-1,y,MOD))*inv2)%MOD;
    x--;
  }
  while(x<=len-1){
    ways=(2ll*ways-nCr(x,y,MOD)+MOD)%MOD;
    x++;
  }
  while(y<=on_left-1){
    ways=(ways+nCr(x,y+1,MOD))%MOD;
    y++;
  }
  return ways;
}
void solve(){ 
  ll n; cin>>n;
  power[0]=1;
  vector<array<ll,2>> track;
  multiset<ll> consider;
  for(ll i=1;i<=n;i++){
    cin>>l[i]>>r[i];
    track.push_back({r[i],l[i]});
    consider.insert(l[i]);
    power[i]=(power[i-1]*2ll)%MOD;
  }
  ans=on_left=0;
  on_right=len=n;
  x=y=0; ways=1;
  sort(all(track));
  for(auto it:track){
    while(!consider.empty()){
      if(*consider.begin() <= it[0]){
        consider.erase(consider.begin());
        on_right--,len--;
      }
      else{
        break;
      }
    }
    ll now=power[len]-getv();
    now=(now*power[n-1-len])%MOD;
    now=(now*it[0])%MOD;
    ans=(ans+MOD-now)%MOD;
    on_left++,len++;
  }
  track.clear(); consider.clear();
  for(ll i=1;i<=n;i++){
    track.push_back({l[i],r[i]});
    consider.insert(r[i]);
  }
  sort(all(track));
  reverse(all(track));
  on_left=0;
  on_right=len=n;
  x=y=0; ways=1;
  for(auto it:track){
    while(!consider.empty()){
      if(*(--consider.end()) >= it[0]){
        consider.erase(--consider.end());
        on_right--,len--;
      }
      else{
        break;
      }
    }
    ll now=power[len]-getv();
    now=(now*power[n-1-len])%MOD;
    now=(now*it[0])%MOD;
    ans=(ans+now)%MOD;
    on_left++,len++;
  }
  ans=(ans+MOD)%MOD;
  cout<<ans<<nline;
  return;    
}  
int main()                                                                                 
{         
  ios_base::sync_with_stdio(false);                         
  cin.tie(NULL);                              
  ll test_cases=1;                 
  cin>>test_cases;
  precompute(MOD);
  inv2=inverse(2,MOD);
  while(test_cases--){
    solve();
  }
  cout<<fixed<<setprecision(12);  
  cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
}