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

// ===================================================================
// This file provides a collection of functions implementing Mo's Algorithm
// with updates (also known as Mo's algorithm with modifications).
// It is designed for competitive programming (ECPC / ACPC). Each function
// is ready to be used as a black box.
//
// What is Mo's Algorithm?
//   It is an offline technique that answers range queries (e.g. subarray
//   queries) by dividing the queries into blocks and sorting them cleverly.
//   This minimises the movement of two pointers (L and R) across the array.
//
// What are "updates"?
//   An update is a point modification that changes the value of one element
//   of the array at a specific position. In Mo with updates, we also keep a
//   third pointer "time" that moves forward/backward through the list of
//   updates. The algorithm handles queries that are interleaved with updates.
//
// Important terms:
//   - Query: a request to compute something on a subarray [L, R] at a given
//     "time" (i.e. after a certain number of updates have been applied).
//   - Update: a structure {pos, oldVal, newVal} that changes arr[pos] from
//     oldVal to newVal.
//   - Time: the number of updates that have been performed before a query.
//   - Block size: the size of the blocks used for sorting. For Mo with
//     updates, a typical choice is N^(2/3) (where N is the array size).
//   - Coordinate compression: mapping large values to a smaller range to
//     use a frequency array efficiently.
//
// Time complexity: O((N + Q) * N^(2/3)) approximately, where N is the array
// size and Q is the number of queries. With optimisations it can be fast
// enough for typical constraints (N, Q <= 1e5).
// ===================================================================

// ===================================================================
// 1) Data Structures for Mo with Updates
// ===================================================================

// Represents one point update:
//   pos    : index in the array (0-based)
//   oldVal : value before the update
//   newVal : value after the update
struct Update {
    int pos;
    int oldVal;
    int newVal;
};

// Represents one query:
//   L, R  : inclusive range [L, R] (0‑based)
//   idx   : original index of the query (used to store the answer)
//   time  : number of updates that must be applied before answering this query
//          (i.e. the index in the updates list up to which we need to apply)
struct Query {
    int L, R;
    int idx;
    int time;
};

// Global block size used for sorting queries.
// It should be set to pow(N, 2.0/3.0) + 1 before sorting.
int MO_BLOCK;

// Comparator used to sort queries for Mo's algorithm with updates.
// Sorts by block of L, then block of R (with alternating direction),
// then time (also alternating for speed).
bool moComparator(const Query& a, const Query& b) {
    int blockL_a = a.L / MO_BLOCK;
    int blockL_b = b.L / MO_BLOCK;
    if (blockL_a != blockL_b) return blockL_a < blockL_b;

    int blockR_a = a.R / MO_BLOCK;
    int blockR_b = b.R / MO_BLOCK;
    if (blockR_a != blockR_b) {
        // alternate direction of R blocks to reduce movement
        return (blockR_a & 1) ? blockR_a > blockR_b : blockR_a < blockR_b;
    }

    // alternate direction of time as well
    return (blockR_a & 1) ? a.time > b.time : a.time < b.time;
}

// ===================================================================
// 2) Helper Functions for Updates and Compression
// ===================================================================

// Applies a single update to the array (without changing any query state).
// This is used to prepare the array before building queries, or to
// revert the array after we finish.
void applyUpdateToArray(vector<int>& arr, const Update& up) {
    arr[up.pos] = up.newVal;
}

// Given a list of changes (pos, newVal) in chronological order, this
// function builds a vector of Update structures and fills the oldVal
// automatically from the current array state. It also modifies the array
// to the final state (applies all changes).
//
// Example:
//   vector<pair<int,int>> changes = {{0, 5}, {2, 10}};
//   vector<Update> updates = prepareUpdates(arr, changes);
//   // now arr has been updated, and updates[0].oldVal is the original arr[0]
vector<Update> prepareUpdates(vector<int>& arr, const vector<pair<int,int>>& changes) {
    vector<Update> updates;
    for (auto [pos, newVal] : changes) {
        updates.push_back({pos, arr[pos], newVal});
        arr[pos] = newVal;
    }
    return updates;
}

// Coordinate compression: maps all values that appear in the array and
// in the updates to a smaller set of integers [0 .. M-1]. This is useful
// when values are large, because we can use a vector<int> as frequency array.
// This function modifies arr and updates in place.
void compressArray(vector<int>& arr, vector<Update>& updates) {
    vector<int> vals = arr;
    for (auto& u : updates) {
        vals.push_back(u.oldVal);
        vals.push_back(u.newVal);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    for (int& x : arr) {
        x = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
    }
    for (auto& u : updates) {
        u.oldVal = lower_bound(vals.begin(), vals.end(), u.oldVal) - vals.begin();
        u.newVal = lower_bound(vals.begin(), vals.end(), u.newVal) - vals.begin();
    }
}

// ===================================================================
// 3) Ready‑Made Functions for Common Query Types
//    Each function is self‑contained and returns a vector of answers.
//    They all assume that the queries vector has the correct idx and time.
//    If values are large, call compressArray() before calling these functions.
// ===================================================================

// -------------------------------------------------------------------
// 4.1) Count distinct elements in each query range [L, R] with updates.
//      Purpose: For each query, returns the number of different values
//               that appear in the subarray arr[L..R] at that time.
//      Parameters:
//        - arr: vector of integers (passed by value; the function modifies it)
//        - updates: vector of Update structures in chronological order
//        - queries: vector of Query structures (must be filled with L,R,idx,time)
//      Returns:
//        - vector<int> answers, where answers[i] = distinct count for query i.
//      Time complexity: O((N+Q) * N^(2/3)) approximately.
//      Constraints:
//        - arr values and update values should be compressed (small integers)
//          or a large frequency array may be used (not recommended).
//      Notes:
//        - The function sorts the queries internally, so the order of queries
//          in the input vector is not preserved.
//        - The array is modified during processing but restored to the final
//          state (all updates applied) after finishing.
// -------------------------------------------------------------------
vector<int> distinctWithUpdates(vector<int> arr, const vector<Update>& updates, vector<Query> queries) {
    int n = (int)arr.size();
    int q = (int)queries.size();
    vector<int> ans(q);

    // Determine the maximum value to size the frequency array.
    // If values are not compressed, this could be huge. Use compressArray first.
    int maxVal = 0;
    for (int x : arr) maxVal = max(maxVal, x);
    for (auto& u : updates) maxVal = max(maxVal, max(u.oldVal, u.newVal));
    vector<int> freq(maxVal + 1, 0);

    int curL = 0, curR = -1;          // current window [curL, curR]
    int curTime = 0;                  // number of applied updates
    int distinct = 0;                 // current distinct count

    auto add = [&](int idx) {
        int val = arr[idx];
        if (freq[val] == 0) distinct++;
        freq[val]++;
    };

    auto remove = [&](int idx) {
        int val = arr[idx];
        freq[val]--;
        if (freq[val] == 0) distinct--;
    };

    // Apply or revert one update (forward == true => apply, false => revert)
    auto apply = [&](const Update& up, bool forward) {
        int pos = up.pos;
        int oldVal = up.oldVal;
        int newVal = up.newVal;
        if (forward) {
            // If the update position is inside the current window, we must
            // update the frequency structure before changing the array.
            if (curL <= pos && pos <= curR) {
                // remove old value
                freq[oldVal]--;
                if (freq[oldVal] == 0) distinct--;
                // add new value
                if (freq[newVal] == 0) distinct++;
                freq[newVal]++;
            }
            arr[pos] = newVal;
        } else {
            // revert: undo the update
            if (curL <= pos && pos <= curR) {
                // remove new value
                freq[newVal]--;
                if (freq[newVal] == 0) distinct--;
                // add old value
                if (freq[oldVal] == 0) distinct++;
                freq[oldVal]++;
            }
            arr[pos] = oldVal;
        }
    };

    // Set block size and sort queries
    MO_BLOCK = (int)pow(n, 2.0/3.0) + 1;
    sort(queries.begin(), queries.end(), moComparator);

    // Process queries
    for (const Query& qry : queries) {
        // Move time forward/backward
        while (curTime < qry.time) {
            apply(updates[curTime], true);
            curTime++;
        }
        while (curTime > qry.time) {
            curTime--;
            apply(updates[curTime], false);
        }
        // Move L and R pointers
        while (curL > qry.L) add(--curL);
        while (curR < qry.R) add(++curR);
        while (curL < qry.L) remove(curL++);
        while (curR > qry.R) remove(curR--);
        ans[qry.idx] = distinct;
    }

    return ans;
}

// -------------------------------------------------------------------
// 4.2) Sum of elements in each query range [L, R] with updates.
//      Purpose: Returns the sum of arr[i] for i in [L, R] at the query time.
//      Parameters: same as distinctWithUpdates.
//      Returns: vector<long long> answers (sums may overflow int).
//      Time complexity: O((N+Q) * N^(2/3)).
//      Constraints: same as above.
//      Notes: No compression needed for sums, but values may be large.
// -------------------------------------------------------------------
vector<ll> sumWithUpdates(vector<int> arr, const vector<Update>& updates, vector<Query> queries) {
    int n = (int)arr.size();
    int q = (int)queries.size();
    vector<ll> ans(q);
    int curL = 0, curR = -1, curTime = 0;
    ll sum = 0;

    auto add = [&](int idx) { sum += arr[idx]; };
    auto remove = [&](int idx) { sum -= arr[idx]; };

    auto apply = [&](const Update& up, bool forward) {
        int pos = up.pos;
        int oldVal = up.oldVal;
        int newVal = up.newVal;
        if (forward) {
            if (curL <= pos && pos <= curR) {
                sum -= oldVal;
                sum += newVal;
            }
            arr[pos] = newVal;
        } else {
            if (curL <= pos && pos <= curR) {
                sum -= newVal;
                sum += oldVal;
            }
            arr[pos] = oldVal;
        }
    };

    MO_BLOCK = (int)pow(n, 2.0/3.0) + 1;
    sort(queries.begin(), queries.end(), moComparator);

    for (const Query& qry : queries) {
        while (curTime < qry.time) apply(updates[curTime++], true);
        while (curTime > qry.time) apply(updates[--curTime], false);
        while (curL > qry.L) add(--curL);
        while (curR < qry.R) add(++curR);
        while (curL < qry.L) remove(curL++);
        while (curR > qry.R) remove(curR--);
        ans[qry.idx] = sum;
    }
    return ans;
}

// -------------------------------------------------------------------
// 4.3) Sum of squares of frequencies in each query range.
//      Purpose: For each query, compute sum_{v} freq[v]^2, where freq[v]
//               is the number of occurrences of value v in the subarray.
//               This is useful for counting equal pairs (see 4.5).
//      Parameters: same as distinctWithUpdates.
//      Returns: vector<long long> answers.
//      Time complexity: O((N+Q) * N^(2/3)).
//      Notes: Values should be compressed so that freq array is small.
// -------------------------------------------------------------------
vector<ll> sumSqFreqWithUpdates(vector<int> arr, const vector<Update>& updates, vector<Query> queries) {
    int n = (int)arr.size();
    int q = (int)queries.size();
    vector<ll> ans(q);

    int maxVal = 0;
    for (int x : arr) maxVal = max(maxVal, x);
    for (auto& u : updates) maxVal = max(maxVal, max(u.oldVal, u.newVal));
    vector<int> freq(maxVal + 1, 0);

    int curL = 0, curR = -1, curTime = 0;
    ll sumSq = 0;

    auto add = [&](int idx) {
        int val = arr[idx];
        sumSq += 2LL * freq[val] + 1;   // (f+1)^2 - f^2 = 2f+1
        freq[val]++;
    };

    auto remove = [&](int idx) {
        int val = arr[idx];
        freq[val]--;
        sumSq -= 2LL * freq[val] + 1;   // f^2 - (f-1)^2 = 2f-1, but after decrement
    };

    auto apply = [&](const Update& up, bool forward) {
        int pos = up.pos;
        int oldVal = up.oldVal;
        int newVal = up.newVal;
        if (forward) {
            if (curL <= pos && pos <= curR) {
                // remove old, add new
                freq[oldVal]--;
                sumSq -= 2LL * freq[oldVal] + 1;
                sumSq += 2LL * freq[newVal] + 1;
                freq[newVal]++;
            }
            arr[pos] = newVal;
        } else {
            if (curL <= pos && pos <= curR) {
                // remove new, add old
                freq[newVal]--;
                sumSq -= 2LL * freq[newVal] + 1;
                sumSq += 2LL * freq[oldVal] + 1;
                freq[oldVal]++;
            }
            arr[pos] = oldVal;
        }
    };

    MO_BLOCK = (int)pow(n, 2.0/3.0) + 1;
    sort(queries.begin(), queries.end(), moComparator);

    for (const Query& qry : queries) {
        while (curTime < qry.time) apply(updates[curTime++], true);
        while (curTime > qry.time) apply(updates[--curTime], false);
        while (curL > qry.L) add(--curL);
        while (curR < qry.R) add(++curR);
        while (curL < qry.L) remove(curL++);
        while (curR > qry.R) remove(curR--);
        ans[qry.idx] = sumSq;
    }
    return ans;
}

// -------------------------------------------------------------------
// 4.4) Maximum frequency (mode frequency) in each query range with updates.
//      Purpose: Returns the highest frequency among all values in the subarray.
//      Parameters: same as distinctWithUpdates.
//      Returns: vector<int> answers (maximum frequency).
//      Time complexity: O((N+Q) * N^(2/3)).
//      Notes: Uses an additional frequency‑of‑frequency array to maintain max.
// -------------------------------------------------------------------
vector<int> modeFreqWithUpdates(vector<int> arr, const vector<Update>& updates, vector<Query> queries) {
    int n = (int)arr.size();
    int q = (int)queries.size();
    vector<int> ans(q);

    int maxVal = 0;
    for (int x : arr) maxVal = max(maxVal, x);
    for (auto& u : updates) maxVal = max(maxVal, max(u.oldVal, u.newVal));
    vector<int> freq(maxVal + 1, 0);
    vector<int> freqOfFreq(n + 1, 0); // freqOfFreq[f] = number of values with frequency f
    int curL = 0, curR = -1, curTime = 0;
    int maxFreq = 0;

    auto add = [&](int idx) {
        int val = arr[idx];
        int f = freq[val];
        if (f > 0) freqOfFreq[f]--;
        freq[val]++;
        freqOfFreq[f + 1]++;
        maxFreq = max(maxFreq, f + 1);
    };

    auto remove = [&](int idx) {
        int val = arr[idx];
        int f = freq[val];
        freqOfFreq[f]--;
        if (f == maxFreq && freqOfFreq[f] == 0) {
            // decrease maxFreq until there is at least one value with that frequency
            while (maxFreq > 0 && freqOfFreq[maxFreq] == 0) maxFreq--;
        }
        freq[val]--;
        freqOfFreq[f - 1]++;
    };

    auto apply = [&](const Update& up, bool forward) {
        int pos = up.pos;
        int oldVal = up.oldVal;
        int newVal = up.newVal;
        if (forward) {
            if (curL <= pos && pos <= curR) {
                // remove old
                int f = freq[oldVal];
                freqOfFreq[f]--;
                if (f == maxFreq && freqOfFreq[f] == 0) {
                    while (maxFreq > 0 && freqOfFreq[maxFreq] == 0) maxFreq--;
                }
                freq[oldVal]--;
                freqOfFreq[f - 1]++;

                // add new
                f = freq[newVal];
                if (f > 0) freqOfFreq[f]--;
                freq[newVal]++;
                freqOfFreq[f + 1]++;
                maxFreq = max(maxFreq, f + 1);
            }
            arr[pos] = newVal;
        } else {
            if (curL <= pos && pos <= curR) {
                // remove new
                int f = freq[newVal];
                freqOfFreq[f]--;
                if (f == maxFreq && freqOfFreq[f] == 0) {
                    while (maxFreq > 0 && freqOfFreq[maxFreq] == 0) maxFreq--;
                }
                freq[newVal]--;
                freqOfFreq[f - 1]++;

                // add old
                f = freq[oldVal];
                if (f > 0) freqOfFreq[f]--;
                freq[oldVal]++;
                freqOfFreq[f + 1]++;
                maxFreq = max(maxFreq, f + 1);
            }
            arr[pos] = oldVal;
        }
    };

    MO_BLOCK = (int)pow(n, 2.0/3.0) + 1;
    sort(queries.begin(), queries.end(), moComparator);

    for (const Query& qry : queries) {
        while (curTime < qry.time) apply(updates[curTime++], true);
        while (curTime > qry.time) apply(updates[--curTime], false);
        while (curL > qry.L) add(--curL);
        while (curR < qry.R) add(++curR);
        while (curL < qry.L) remove(curL++);
        while (curR > qry.R) remove(curR--);
        ans[qry.idx] = maxFreq;
    }
    return ans;
}

// -------------------------------------------------------------------
// 4.5) Number of equal pairs (i, j) with L <= i < j <= R in each query.
//      Purpose: Counts unordered pairs of indices within the range that
//               have equal values. This equals (sumSq - len) / 2.
//      Parameters: same as distinctWithUpdates.
//      Returns: vector<long long> answers (number of pairs).
//      Time complexity: O((N+Q) * N^(2/3)).
// -------------------------------------------------------------------
vector<ll> countPairsEqualWithUpdates(vector<int> arr, const vector<Update>& updates, vector<Query> queries) {
    int n = (int)arr.size();
    int q = (int)queries.size();
    vector<ll> ans(q);

    int maxVal = 0;
    for (int x : arr) maxVal = max(maxVal, x);
    for (auto& u : updates) maxVal = max(maxVal, max(u.oldVal, u.newVal));
    vector<int> freq(maxVal + 1, 0);

    int curL = 0, curR = -1, curTime = 0;
    ll sumSq = 0;

    auto add = [&](int idx) {
        int val = arr[idx];
        sumSq += 2LL * freq[val] + 1;
        freq[val]++;
    };
    auto remove = [&](int idx) {
        int val = arr[idx];
        freq[val]--;
        sumSq -= 2LL * freq[val] + 1;
    };
    auto apply = [&](const Update& up, bool forward) {
        int pos = up.pos;
        int oldVal = up.oldVal;
        int newVal = up.newVal;
        if (forward) {
            if (curL <= pos && pos <= curR) {
                freq[oldVal]--;
                sumSq -= 2LL * freq[oldVal] + 1;
                sumSq += 2LL * freq[newVal] + 1;
                freq[newVal]++;
            }
            arr[pos] = newVal;
        } else {
            if (curL <= pos && pos <= curR) {
                freq[newVal]--;
                sumSq -= 2LL * freq[newVal] + 1;
                sumSq += 2LL * freq[oldVal] + 1;
                freq[oldVal]++;
            }
            arr[pos] = oldVal;
        }
    };

    MO_BLOCK = (int)pow(n, 2.0/3.0) + 1;
    sort(queries.begin(), queries.end(), moComparator);

    for (const Query& qry : queries) {
        while (curTime < qry.time) apply(updates[curTime++], true);
        while (curTime > qry.time) apply(updates[--curTime], false);
        while (curL > qry.L) add(--curL);
        while (curR < qry.R) add(++curR);
        while (curL < qry.L) remove(curL++);
        while (curR > qry.R) remove(curR--);
        ll len = qry.R - qry.L + 1;
        ans[qry.idx] = (sumSq - len) / 2;
    }
    return ans;
}

// -------------------------------------------------------------------
// 4.6) Mode value (the most frequent element) in each query range.
//      This function returns the actual value (not just its frequency)
//      that appears most often. If there are ties, the smallest value
//      is returned.
//      Parameters: same as distinctWithUpdates.
//      Returns: vector<int> answers (the value, not the frequency).
//      Time complexity: O((N+Q) * N^(2/3) * log N) because we use std::set
//                       internally to maintain sets of values per frequency.
//      Notes: Values must be compressed for efficiency.
// -------------------------------------------------------------------
vector<int> modeValueWithUpdates(vector<int> arr, const vector<Update>& updates, vector<Query> queries) {
    int n = (int)arr.size();
    int q = (int)queries.size();
    vector<int> ans(q);

    int maxVal = 0;
    for (int x : arr) maxVal = max(maxVal, x);
    for (auto& u : updates) maxVal = max(maxVal, max(u.oldVal, u.newVal));
    vector<int> freq(maxVal + 1, 0);
    vector<set<int>> valuesAtFreq(n + 1); // values that have this frequency
    int curL = 0, curR = -1, curTime = 0;
    int maxFreq = 0;
    int modeValue = 0; // current value with maximum frequency

    auto add = [&](int idx) {
        int val = arr[idx];
        int f = freq[val];
        if (f > 0) valuesAtFreq[f].erase(val);
        freq[val]++;
        valuesAtFreq[f + 1].insert(val);
        if (f + 1 > maxFreq) {
            maxFreq = f + 1;
            modeValue = *valuesAtFreq[maxFreq].begin();
        }
    };

    auto remove = [&](int idx) {
        int val = arr[idx];
        int f = freq[val];
        valuesAtFreq[f].erase(val);
        freq[val]--;
        if (f - 1 > 0) valuesAtFreq[f - 1].insert(val);
        if (f == maxFreq && valuesAtFreq[maxFreq].empty()) {
            while (maxFreq > 0 && valuesAtFreq[maxFreq].empty()) maxFreq--;
            if (maxFreq > 0) modeValue = *valuesAtFreq[maxFreq].begin();
            else modeValue = 0;
        } else if (f == maxFreq && !valuesAtFreq[maxFreq].empty()) {
            // There are other values with the same max frequency.
            modeValue = *valuesAtFreq[maxFreq].begin();
        }
        // If f < maxFreq, modeValue remains unchanged.
    };

    auto apply = [&](const Update& up, bool forward) {
        int pos = up.pos;
        int oldVal = up.oldVal;
        int newVal = up.newVal;
        if (forward) {
            if (curL <= pos && pos <= curR) {
                // remove oldVal from current window
                int f = freq[oldVal];
                valuesAtFreq[f].erase(oldVal);
                freq[oldVal]--;
                if (f - 1 > 0) valuesAtFreq[f - 1].insert(oldVal);
                if (f == maxFreq && valuesAtFreq[maxFreq].empty()) {
                    while (maxFreq > 0 && valuesAtFreq[maxFreq].empty()) maxFreq--;
                    if (maxFreq > 0) modeValue = *valuesAtFreq[maxFreq].begin();
                    else modeValue = 0;
                } else if (f == maxFreq && !valuesAtFreq[maxFreq].empty()) {
                    modeValue = *valuesAtFreq[maxFreq].begin();
                }

                // add newVal
                f = freq[newVal];
                if (f > 0) valuesAtFreq[f].erase(newVal);
                freq[newVal]++;
                valuesAtFreq[f + 1].insert(newVal);
                if (f + 1 > maxFreq) {
                    maxFreq = f + 1;
                    modeValue = *valuesAtFreq[maxFreq].begin();
                }
            }
            arr[pos] = newVal;
        } else {
            if (curL <= pos && pos <= curR) {
                // remove newVal
                int f = freq[newVal];
                valuesAtFreq[f].erase(newVal);
                freq[newVal]--;
                if (f - 1 > 0) valuesAtFreq[f - 1].insert(newVal);
                if (f == maxFreq && valuesAtFreq[maxFreq].empty()) {
                    while (maxFreq > 0 && valuesAtFreq[maxFreq].empty()) maxFreq--;
                    if (maxFreq > 0) modeValue = *valuesAtFreq[maxFreq].begin();
                    else modeValue = 0;
                } else if (f == maxFreq && !valuesAtFreq[maxFreq].empty()) {
                    modeValue = *valuesAtFreq[maxFreq].begin();
                }

                // add oldVal
                f = freq[oldVal];
                if (f > 0) valuesAtFreq[f].erase(oldVal);
                freq[oldVal]++;
                valuesAtFreq[f + 1].insert(oldVal);
                if (f + 1 > maxFreq) {
                    maxFreq = f + 1;
                    modeValue = *valuesAtFreq[maxFreq].begin();
                }
            }
            arr[pos] = oldVal;
        }
    };

    MO_BLOCK = (int)pow(n, 2.0/3.0) + 1;
    sort(queries.begin(), queries.end(), moComparator);

    for (const Query& qry : queries) {
        while (curTime < qry.time) apply(updates[curTime++], true);
        while (curTime > qry.time) apply(updates[--curTime], false);
        while (curL > qry.L) add(--curL);
        while (curR < qry.R) add(++curR);
        while (curL < qry.L) remove(curL++);
        while (curR > qry.R) remove(curR--);
        ans[qry.idx] = modeValue;
    }
    return ans;
}

// ===================================================================
// 5) Tips and Tricks for Mo with Updates (ECPC / ACPC patterns)
// ===================================================================

/*
  - If the array values are large, always call compressArray() before
    using any of the functions that rely on a frequency array.
  - Choose block size carefully: N^(2/3) works well, but you can also
    experiment with other powers.
  - The comparator alternates directions to improve cache locality.
  - For problems where there are no updates, you can use the simpler
    Mo's algorithm (without time) which is faster. The functions above
    handle the general case.
  - The generic template (moSolverGeneric) is not fully provided, but
    you can copy the code from any ready‑made function and change the
    add/remove/apply logic to match your property.
  - Common properties that are easy to maintain with MO:
      * sum, product, min, max (with appropriate updates)
      * distinct count
      * frequency moments (sum of freq^k)
      * number of pairs with equal values
      * mode frequency
      * median? (not recommended)
  - If you need to handle multiple test cases, reinitialize all global
    variables or call functions with local state (as done above).
*/

// ===================================================================
// 6) Example Usage (main)
//    This shows how to use the functions above.
// ===================================================================

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Example: array of size 5, values [1, 2, 1, 3, 2]
    vector<int> arr = {1, 2, 1, 3, 2};

    // Updates: change arr[1] to 5, then arr[3] to 4
    // We manually build the updates (oldVal must be known from original array).
    vector<Update> updates;
    updates.push_back({1, 2, 5}); // change arr[1] from 2 to 5
    updates.push_back({3, 3, 4}); // change arr[3] from 3 to 4

    // Queries:
    // Query 0: at time 0 (no updates applied), range [0, 2] -> should be [1,2,1]
    // Query 1: at time 1 (first update applied), range [1, 3] -> after first update: [1,5,1,3,2] -> [5,1,3]
    // Query 2: at time 2 (both updates applied), range [0, 4] -> [1,5,1,4,2]
    vector<Query> queries;
    queries.push_back({0, 2, 0, 0});
    queries.push_back({1, 3, 1, 1});
    queries.push_back({0, 4, 2, 2});

    // Call distinctWithUpdates
    vector<int> distinctAns = distinctWithUpdates(arr, updates, queries);
    cout << "Distinct answers:\n";
    for (int i = 0; i < (int)distinctAns.size(); i++) {
        cout << "Query " << i << ": " << distinctAns[i] << "\n";
    }

    // Test sumWithUpdates
    vector<ll> sumAns = sumWithUpdates(arr, updates, queries);
    cout << "\nSum answers:\n";
    for (int i = 0; i < (int)sumAns.size(); i++) {
        cout << "Query " << i << ": " << sumAns[i] << "\n";
    }

    // Test pairs equal
    vector<ll> pairsAns = countPairsEqualWithUpdates(arr, updates, queries);
    cout << "\nEqual pairs answers:\n";
    for (int i = 0; i < (int)pairsAns.size(); i++) {
        cout << "Query " << i << ": " << pairsAns[i] << "\n";
    }

    return 0;
}

// ===================================================================
// End of Mo with Updates template
// ===================================================================