Hello Codeforces!

Notice that if $$$s$$$ starts with a $$$1$$$ we must move the entire string $$$s$$$ to $$$t$$$ at some point. Also Notice that if we perform the operation, the total number of occurrences of $$$01$$$ and $$$10$$$ across both strings can only decrease by one. This gives us an upper bound on the answer being the number of occurrences of $$$01$$$ and $$$10$$$ in $$$s$$$ adding one to this if it starts with the character $$$1$$$.

Now the following construction uses the same number of moves as the upper bound (thus showing it is the minimum number of moves): If $$$s$$$ begins with $$$1$$$ then select the entire string $$$s$$$ and move it to $$$t$$$. Then repeatedly find the first character in $$$s$$$ or $$$t$$$ which is not equal to the character before it (note under this construction such an index can only exist in one string at a time) and selected the suffix starting from this character and move it to the other string. During this construction some prefix of $$$s$$$ will contain $$$0$$$s and some prefix of $$$t$$$ will contain $$$1$$$s, so after each move the total number of $$$01$$$ and $$$10$$$ will decrease.

So the answer to this problem will be the number of $$$01$$$ and $$$10$$$ in $$$s$$$ adding one to the answer if it starts with $$$1$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void solve(){
    int n;
    cin >> n;
    
    string s;
    cin >> s;
    
    int ans = 0;
    for (int i = 0; i < n - 1; i++) {
        if (s[i] != s[i + 1]) ans++;
    }

    if (s[0] == '1') ans++;
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

The first thing to notice is that if we remove an element from $$$a$$$ then our score will never increase. Because removing one element will cause $$$|a|$$$ to decrease by $$$1$$$ and $$$\mathrm{distinct}(a)$$$ will decrease by at most $$$1$$$ and so the $$$|a|$$$ — $$$\mathrm{distinct}(a)$$$ will never increase. This means that we should be trying to removing the longest subarray which does not decrease our score.

We can see that removing any element which only occurs once in $$$a$$$ will never decrease our score, and that removing any element which occurs more than once will always decrease our score. Thus we should try to find the longest subarray of elements which only have $$$1$$$ occurrence in $$$a$$$ and this will be the answer. This can be calculated with a single loop in $$$O(n)$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void solve(){
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    vector<int> freq(n + 1);
    for (int x : a) freq[x]++;

    vector<int> len(n + 1);
    len[0] = freq[a[0]] == 1;
    for (int i = 1; i < n; i++)
        if (freq[a[i]] == 1)
            len[i] = len[i - 1] + 1;
    
    int mx = *max_element(len.begin(), len.end());
    if (mx == 0){
        cout << "0\n";
        return;
    }

    for (int i = 0; i < n; i++){
        if (len[i] == mx){
            cout << i - len[i] + 2 << " " << i + 1 << "\n";
            return;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

First see that at any point we should either remove the leftmost positive element or the rightmost negative element, as if we were to take a positive element that is not the leftmost one we could have just taken the leftmost one first and had a higher score, a similar argument can be made for taking the rightmost negative element. Now if you do either of these moves some number of times you will always take some prefix of positive numbers and then the remaining suffix of negative numbers, and so to calculate the answer we only need to check all $$$n + 1$$$ ways to split the array into a prefix and suffix and take the maximum across them all which is easy to do in $$$O(n)$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void solve(){
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a)
        cin >> x;

    vector<ll> pre(n), suf(n);
    if (a[0] > 0)
        pre[0] = a[0];

    for (int i = 1; i < n; i++){
        pre[i] = pre[i - 1];
        if (a[i] > 0)
            pre[i] += a[i];
    }

    if (a[n - 1] < 0)
        suf[n - 1] = -a[n - 1];
    
    for (int i = n - 2; i >= 0; i--){
        suf[i] = suf[i + 1];
        if (a[i] < 0)
            suf[i] -= a[i];
    }

    ll ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, pre[i] + suf[i]);
    
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

First notice that if we are unable to eat the next slime then this slime must have had a $$$\mathrm{msb}$$$ (most significant bit) at least as large as the current value of $$$x$$$. Subsequently this means that if a slime has a $$$\mathrm{msb}$$$ strictly less than $$$x$$$ we can always eat it.

Now see that if we eat a slime with lower $$$\mathrm{msb}$$$ than $$$x$$$ then the $$$\mathrm{msb}$$$ of $$$x$$$ will never decrease and that if we eat a slime with equal $$$\mathrm{msb}$$$ then $$$\mathrm{msb}$$$ of $$$x$$$ will decrease, this inspires us to do the following:

at any point we should eat as many slimes as we can to the left that have smaller $$$\mathrm{msb}$$$ (to calculate the new value of $$$x$$$ after doing this we can just do any range xor query such as prefix sums), after this the next slime will always have $$$\mathrm{msb}$$$ greater than or equal to $$$x$$$ and so we will either not be able to eat it or we will eat it $$$\mathrm{msb}$$$ of $$$x$$$ will decrease. Because the $$$\mathrm{msb}$$$ will always decrease after every operation we will only need to do this operation at most $$$log(x)$$$ times!

And so we should try find some way to calculate fast the first slime to our left with $$$\mathrm{msb}$$$ greater than or equal to the current $$$\mathrm{msb}$$$ of $$$x$$$. There are many ways to do this but I would say the cleanest way is to use prefix sums, store for each $$$i, j$$$ where $$$1 \le i \le n, 1 \le j \le log(W)$$$ (where $$$W$$$ is the max value of $$$w_i$$$ and $$$x$$$), the greatest index before it which has $$$\mathrm{msb}$$$ greater than or equal to $$$j$$$ call this $$$\mathrm{pre}_{i, j}$$$

Now we can update it as follows:

• if $$$\mathrm{msb}(w_i) < j$$$ then $$$\mathrm{pre}_{i, j} = \mathrm{pre}_{i - 1, j}$$$

• else $$$\mathrm{pre}_{i, j} = i$$$

And so the final complexity is $$$O((n + q)log(W))$$$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

const int W = 30;

void solve(){
    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int &x : a) cin >> x;
    
    vector<int> pre(n + 1);
    pre[0] = a[0];
    for (int i = 1; i < n; i++){
        pre[i] = pre[i - 1] ^a[i];
    }

    vector<array<int, W>> last(n);
    for (int i = 0; i < n; i++){
            fill(last[i].begin(), last[i].end(), 0);
        if (i > 0) last[i] = last[i - 1];
        last[i][__lg(a[i])] = i;

        for (int j = W - 2; j >= 0; j--){
            last[i][j] = max(last[i][j], last[i][j + 1]);
        }
    }

    while (q--) {
        int x;
        cin >> x;

        int idx = n - 1;
        while (idx >= 0 && x > 0){
            int msb = __lg(x);

            int nxt = last[idx][msb];
            x ^= pre[idx] ^ pre[nxt];
            idx = nxt;
            if (nxt == -1 || a[nxt] > x) break;

            x ^= a[nxt];
            idx--;
        }

        cout << n - idx - 1 << "\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

The first thing to notice is that the first column of sand will be identical to $$$c$$$ after sorting. This means that it must be true that $$$c' = c$$$.

Now that we know $$$c' = c$$$ we need to find how many ways we can re-arrange $$$p$$$ such that the sand layout is the same. Something we can notice is that $$$p'$$$ must be able to obtainable from $$$p$$$ by only swapping values of the same colour. This is true because if we remove all sand blocks that are not of any specific colour (i.e. keeping only one colour), then by examining the new sand layout we can find what the values of the colour we didn't remove are.

Now lets isolate a single colour and try to find the number of ways we can arrange it. One thing we can notice is that we can swap an arbitrary $$$p_i$$$ and $$$p_j$$$ without changing the final sand layout if and only if every number of different colour between $$$i$$$ and $$$j$$$ is strictly less than both $$$p_i$$$ and $$$p_j$$$. After staring at this operation enough you will see that each number in $$$p_i$$$ has a certain range of positions it can take. I think the easiest way to calculate this range is to use DSU, iterate in order of $$$p_i$$$ and merge with everything it can reach in one move, storing leftmost and rightmost element currently in the component to be fast enough.

It is important to note that these ranges we are calculating have some form of tree structure, because of how we calculated them every pair of ranges will either not intersect or one will contain the other. This means that if we iterate in order of size and "fix" a position in each range we will calculate the answer.

There is actually no need to build the tree, and instead we can multiply by the size of each DSU component as we are merging, after each merge decreasing the size of the component by $$$1$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

const int MOD = 998244353;

template<ll mod> // template was not stolen from https://codeforces.me/profile/SharpEdged
struct modnum {
    static constexpr bool is_big_mod = mod > numeric_limits<int>::max();

    using S = conditional_t<is_big_mod, ll, int>;
    using L = conditional_t<is_big_mod, __int128, ll>;

    S x;

    modnum() : x(0) {}
    modnum(ll _x) {
        _x %= static_cast<ll>(mod);
        if (_x < 0) { _x += mod; }
        x = _x;
    }

    modnum pow(ll n) const {
        modnum res = 1;
        modnum cur = *this;
        while (n > 0) {
            if (n & 1) res *= cur;
            cur *= cur;
            n /= 2;
        }
        return res;
    }
    modnum inv() const { return (*this).pow(mod-2); }
    
    modnum& operator+=(const modnum& a){
        x += a.x;
        if (x >= mod) x -= mod;
        return *this;
    }
    modnum& operator-=(const modnum& a){
        if (x < a.x) x += mod;
        x -= a.x;
        return *this;
    }
    modnum& operator*=(const modnum& a){
        x = static_cast<L>(x) * a.x % mod;
        return *this;
    }
    modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
    
    friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
    friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
    friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
    friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
    
    friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
    friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
    friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }

    friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
    friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
};

using mint = modnum<MOD>;

template <class T> struct SegTree{
    vector<T> seg;
    int n;
    const T ID = 0;
    
    T cmb(T a, T b){
        return max(a, b);
    }
    
    SegTree(int _n){
        n = 1;
        while (n < _n) n *= 2;
        seg.assign(2 * n + 1, ID);
    }
    
    void set(int pos, T val){
        seg[pos + n] = val;
    }
    
    void build(){
        for (int i = n - 1; i >= 1; i--) seg[i] = cmb(seg[2 * i], seg[2 * i + 1]);
    }
    
    void upd(int v, int tl, int tr, int pos, T val){
        if (tl == tr){
            seg[v] = val;
        } else {
            int tm = (tl + tr) / 2;
            if (pos <= tm) upd(2 * v, tl, tm, pos, val);
            else upd(2 * v + 1, tm + 1, tr, pos, val);
            seg[v] = cmb(seg[2 * v], seg[2 * v + 1]);
        }
    }
    
    void upd(int pos, T val){
        upd(1, 0, n - 1, pos, val);
    }
    
    T query(int v, int tl, int tr, int l, int r){
        if (l > r) return ID;
        if (l == tl && r == tr) return seg[v];
        int tm = (tl + tr) / 2;
        T res = query(2 * v, tl, tm, l, min(tm, r));
        res = cmb(res, query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
        return res;
    }
    
    T query(int l, int r){
        return query(1, 0, n - 1, l, r);
    }
};

struct DSU{
    vector<int> p, sz, used, mn, mx;
    
    DSU(int n){
        p.assign(n, 0);
        sz.assign(n, 1);
        used.assign(n, 0);
        mx.assign(n, 0);
        mn.assign(n, 0);

        for (int i = 0; i < n; i++) p[i] = i;
    }
    
    int find(int u){
        if (p[u] == u) return u;
        p[u] = find(p[u]);
        return p[u];
    }
    
    void unite(int u, int v){
        u = find(u);
        v = find(v);
        if (u == v) return;
        
        if (sz[u] < sz[v]) swap(u, v);
        p[v] = u;
        sz[u] += sz[v];
        used[u] += used[v];
        mn[u] = min(mn[u], mn[v]);
        mx[u] = max(mx[u], mx[v]);
    }
    
    bool same(int u, int v){
        return find(u) == find(v);
    }
    
    int size(int u){
        u = find(u);
        return sz[u];
    }
};

void solve(){
    int n;
    cin >> n;

    vector<int> a(n), b(n);
    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;

    vector<vector<int>> col(n + 1);
    for (int i = 0; i < n; i++){
        col[b[i]].push_back(i);
    }

    vector<vector<int>> ord(n + 1);

    for (int i = 0; i <= n; i++){
        ord[i] = col[i];
        sort(ord[i].begin(), ord[i].end(), [&](int x, int y) -> bool{
            return a[x] < a[y];
        });
    }

    SegTree<int> seg(n);
    for (int i = 0; i < n; i++){
        seg.set(i, a[i]);
    } seg.build();

    mint ans = 1;
    DSU dsu(n);
    for (int i = 0; i <= n; i++){
        for (int j = 0; j < col[i].size(); j++){
            dsu.mn[col[i][j]] = j;
            dsu.mx[col[i][j]] = j;
        }
    }

    for (int i = 0; i <= n; i++){
        for (int x : ord[i]) seg.upd(x, 0);

        for (int x : ord[i]){
            int idx = lower_bound(col[i].begin(), col[i].end(), x) - col[i].begin();
            for (int j = idx + 1; j < col[i].size(); j++){
                if (seg.query(x, col[i][j]) >= a[x]) break;

                dsu.unite(x, col[i][j]);
                j = dsu.mx[dsu.find(x)];
            }

            for (int j = idx - 1; j >= 0; j--){
                if (seg.query(col[i][j], x) >= a[x]) break;

                dsu.unite(x, col[i][j]);
                j = dsu.mn[dsu.find(x)];
            }

            int u = dsu.find(x);
            ans *= dsu.size(u) - dsu.used[u];
            dsu.used[u]++;
        }

        for (int x : ord[i]) seg.upd(x, a[x]);
    }

    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

For an arbitrary array $$$b$$$ first notice that $$$\min(b_1,\ldots,b_i)$$$ and $$$\max(b_{i + 1},\ldots,n)$$$ is both non-increasing as we increase $$$i$$$. This means that if an array $$$b$$$ is epic then there exists a unique pair of integers $$$x, y$$$ such that $$$x + y = k$$$ and there exists $$$i, (1 \le i < |b|)$$$ such that $$$\min(b_1,\ldots,b_i) = x$$$ and $$$\max(b_{i + 1},\ldots,n) = y$$$.

Lets call an array $$$b$$$ $$$x$$$-epic if it is epic due to the pair $$$x, k - x$$$. Because the pair $$$x, y$$$ is unique, the answer will be equivalent to the sum of all $$$x$$$-epic subarrays of $$$a$$$. So lets try to find this sum.

Lets say we are trying to find the sum of all $$$x$$$ epic subarrays for a given $$$x$$$ and let $$$y = k - x$$$. Firstly the subarray must obviously contain both $$$x$$$ and $$$y$$$, so lets try to find for each $$$i$$$ the number of subarrays that are epic where $$$a_i$$$ is the first instance of $$$x$$$ in the subarray. Notice that it must be true that the first element smaller than $$$x$$$ must come after the last element bigger than $$$y$$$. Notice also that there cannot be an element bigger than $$$y$$$ after the last instance of $$$y$$$.

So we should store for each index $$$j$$$ such that $$$p_j = y$$$ the length of the longest consecutive sequence of elements strictly less than $$$y$$$, which contains $$$j$$$ as its leftmost element. Then for each $$$i$$$ where $$$p_i = x$$$ we should binary search for the last time where first element smaller than $$$x$$$ after the last element bigger than $$$y$$$. Once we can use prefix sums to find the number of possible right positions of the subarray. To find the number of possible left positions of the subarray it is just the length of the longest consecutive interval which only contains element strictly larger than $$$x$$$ and contain $$$i$$$ as its right most element. Now we know the number of possible left endpoints of the subarray and right endpoints, so we can just add their product to the answer.

After doing this across all $$$i$$$ we will have the answer.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

template <class T> struct SegTree{
    vector<T> seg;
    int n;
    const T ID = {INT_MAX, -INT_MAX};
    
    T cmb(T a, T b){
        array<int, 2> res;
        res[0] = min(a[0], b[0]);
        res[1] = max(a[1], b[1]);
        return res;
    }
    
    SegTree(int _n){
        n = 1;
        while (n < _n) n *= 2;
        seg.assign(2 * n + 1, ID);
    }
    
    void set(int pos, T val){
        seg[pos + n] = val;
    }
    
    void build(){
        for (int i = n - 1; i >= 1; i--) seg[i] = cmb(seg[2 * i], seg[2 * i + 1]);
    }
    
    void upd(int v, int tl, int tr, int pos, T val){
        if (tl == tr){
            seg[v] = val;
        } else {
            int tm = (tl + tr) / 2;
            if (pos <= tm) upd(2 * v, tl, tm, pos, val);
            else upd(2 * v + 1, tm + 1, tr, pos, val);
            seg[v] = cmb(seg[2 * v], seg[2 * v + 1]);
        }
    }
    
    void upd(int pos, T val){
        upd(1, 0, n - 1, pos, val);
    }
    
    T query(int v, int tl, int tr, int l, int r){
        if (l > r) return ID;
        if (l == tl && r == tr) return seg[v];
        int tm = (tl + tr) / 2;
        T res = query(2 * v, tl, tm, l, min(tm, r));
        res = cmb(res, query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
        return res;
    }
    
    T query(int l, int r){
        return query(1, 0, n - 1, l, r);
    }
};

void solve(){
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    vector<vector<int>> p(n + 1);
    for (int i = 0; i < n; i++)
        p[a[i]].push_back(i);
    
    vector<array<int, 2>> stk;
    vector<int> small_l(n, -1), small_r(n, n), big_l(n, -1), big_r(n, n);

    for (int i = 0; i < n; i++){
        while (stk.size() && a[i] <= stk.back()[0])
            stk.pop_back();

        if (stk.size())
            small_l[i] = stk.back()[1];
        stk.push_back({a[i], i});
    }

    stk.clear();
    for (int i = n - 1; i >= 0; i--){
        while (stk.size() && a[i] >= stk.back()[0])
            stk.pop_back();

        if (stk.size())
            big_r[i] = stk.back()[1];
        stk.push_back({a[i], i});
    }

    ll ans = 0;
    SegTree<array<int, 2>> seg_small(n), seg_big(n);

    for (int x = 1; x <= n; x++){
        int y = k - x;
        if (y > n){
            for (int pos : p[x])
                seg_small.upd(pos, {pos, pos});
            continue;
        }

        vector<int> pre(p[y].size());
        for (int i = 0; i < p[y].size(); i++){
            if (i > 0)
                pre[i] += pre[i - 1];

            int r = big_r[p[y][i]] - 1;
            if (i < p[y].size() - 1)
                r = min(r, p[y][i + 1] - 1);
            pre[i] += r - p[y][i] + 1;
        }

        vector<int> first(p[x].size()), last(p[y].size());
        for (int i = 0; i < p[x].size(); i++)
            first[i] = seg_small.query(p[x][i], n - 1)[0];

        for (int i = 0; i < p[y].size(); i++)
            last[i] = seg_big.query(0, p[y][i])[1];

        int prev = -1;
        for (int i = 0; i < p[x].size(); i++){
            int l = p[x][i];
            int l_min = small_l[l] + 1;
            l_min = max(l_min, prev + 1);
            prev = l;

            int nxt = upper_bound(p[y].begin(), p[y].end(), l) - p[y].begin();
            if (nxt == p[y].size())
                continue;
       
            int lo = nxt, hi = p[y].size();
            while (lo < hi){
                int mid = (lo + hi) / 2;

                int pos = p[y][mid];
                if (first[i] <= last[mid])
                    hi = mid;
                else
                    lo = mid + 1;
            }

            lo--;
            if (lo < nxt)
                continue;

            int res = pre[lo];
            if (nxt > 0)
                res -= pre[nxt - 1];

            ans += 1LL * (l - l_min + 1) * res;
        }

        for (int pos : p[x])
            seg_small.upd(pos, {pos, pos});
        for (int pos : p[y])
            seg_big.upd(pos, {pos, pos});
    }

    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}