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

// ===================================================================
// This file contains a collection of Mo's Algorithm (with SQRT trick)
// implementations. Each function is ready to be used as a "black box".
//
// Read the comments above each one to understand:
//   - What it solves
//   - What input it expects
//   - What it returns
//   - Time complexity
//   - Important constraints / assumptions
//
// IMPORTANT TERMS (explained in simple English):
//   - "Offline algorithm" : we need to know ALL queries before we start
//                           answering any of them. We cannot answer them
//                           one by one as they come.
//   - "Query" : a question like "what is the sum of elements from index L to R?".
//   - "Pointer" (L and R) : two integer indices that mark the current range
//                           we are looking at. Moving them updates our answer.
//   - "Block" : we divide the array into groups of size sqrt(N). This is
//               the "SQRT trick" that makes the algorithm fast.
//   - "Add / Remove" : when we move a pointer to include a new element,
//                      we "add" it to our current answer. When we move out
//                      of an element, we "remove" it.
//   - "Frequency array" : an array that counts how many times each value
//                         appears in the current range.
// ===================================================================

// ===================================================================
// 1) Core Structures & Helpers
//    These are the basic building blocks used by all Mo functions below.
// ===================================================================

// 1.1) Represents a single range query.
//      Parameters:
//        - l : left index of the range (0-based or 1-based, but pick one
//              and stick to it. All functions here use 0-based indices).
//        - r : right index of the range (inclusive).
//        - idx : the index of this query in the original list (to store answers).
//      Time complexity: O(1) to create.
struct Query {
    int l, r, idx;
};

// 1.2) Represents an update for "Mo with Updates".
//      Parameters:
//        - pos : the index in the array where the change happens.
//        - oldVal : the value before the update.
//        - newVal : the value after the update.
//      Time complexity: O(1) to create.
struct UpdateQuery {
    int pos, oldVal, newVal;
};

// 1.3) Calculates the optimal block size for standard Mo's algorithm.
//      Parameters:
//        - n : the size of the array.
//        - q : the number of queries (optional, but recommended).
//      Returns:
//        - an integer representing the block size.
//      Time complexity: O(1)
//      Constraint: n must be > 0.
//      Note: using max(1, (int)(n / sqrt(q))) often gives better performance.
int getMoBlockSize(int n, int q) {
    if (q == 0) return max(1, (int)sqrt(n));
    return max(1, (int)(n / sqrt(q)));
}

// 1.4) Sorts queries in the special Mo's order.
//      This is NOT a function you call directly. It is used internally
//      by the process functions.
//      Parameters:
//        - a, b : two Query objects.
//        - blockSize : the block size to use.
//      Returns:
//        - true if 'a' should come before 'b' in the sorted order.
//      Time complexity: O(1)
//      Note: The "even-odd trick" (ordering R differently based on block)
//            reduces pointer movements significantly.
bool moComparator(const Query& a, const Query& b, int blockSize) {
    int blockA = a.l / blockSize;
    int blockB = b.l / blockSize;
    if (blockA != blockB) return blockA < blockB;
    // Even block: sort R ascending. Odd block: sort R descending.
    if (blockA & 1) return a.r > b.r;
    return a.r < b.r;
}

// ===================================================================
// 2) Standard Mo's Algorithm (No Updates)
//    These functions answer static range queries on an array.
//    They all expect the array to be 0-indexed.
// ===================================================================

// 2.1) Count the number of distinct elements in each query range.
//      Purpose:
//        - Given an array and many queries [L, R], for each query,
//          tell how many different values appear in that subarray.
//      Parameters:
//        - arr : the input vector of integers (0-indexed).
//        - queries : a vector of Query structs. Each Query must have
//                    'l', 'r', and 'idx' filled. 'idx' identifies
//                    which query it is.
//      Returns:
//        - a vector<int> where answer[i] is the number of distinct elements
//          in the i-th query (ordered by the original query index).
//      Time complexity: O((N + Q) * sqrt(N)) on average, where N = arr.size(),
//                       Q = queries.size(). More precisely O((N+Q) * sqrt(N)).
//      Constraint:
//        - The array values should be compressible (coordinate compression
//          is recommended if values are large). This function does NOT
//          compress internally. If values exceed 1e6, use a different
//          method or compress the array first.
//      Notes:
//        - This is the classic "Mo's algorithm" problem.
//        - If you have negative numbers or large numbers (> 2e5), you MUST
//          compress them (e.g., sort and map to 0..M-1) before calling.
vector<int> moDistinctElements(const vector<int>& arr, const vector<Query>& queries) {
    int n = arr.size();
    int q = queries.size();
    int blockSize = getMoBlockSize(n, q);

    // Sort the queries in the Mo order.
    vector<Query> sortedQueries = queries;
    sort(sortedQueries.begin(), sortedQueries.end(),
         [&](const Query& a, const Query& b) {
             return moComparator(a, b, blockSize);
         });

    vector<int> ans(q, 0);
    vector<int> freq(200005, 0); // Assumes arr values are < 200k.
    // If your values are larger, compress them or change this size.

    int curL = 0, curR = -1;
    int distinctCount = 0;

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

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

    for (const Query& qry : sortedQueries) {
        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] = distinctCount;
    }
    return ans;
}

// 2.2) Find the sum of elements in each query range.
//      Purpose:
//        - Given an array and many queries [L, R], for each query,
//          calculate the total sum of arr[L] + ... + arr[R].
//      Parameters:
//        - arr : the input vector of long long integers (0-indexed).
//        - queries : a vector of Query structs.
//      Returns:
//        - a vector<long long> where answer[i] is the sum for the i-th query.
//      Time complexity: O((N + Q) * sqrt(N)).
//      Constraint: none, but ensure sums fit in long long.
//      Notes: This is just to show how easy it is to change the "add/remove"
//             logic. You can adapt this pattern for many other problems.
vector<long long> moSumRange(const vector<long long>& arr, const vector<Query>& queries) {
    int n = arr.size();
    int q = queries.size();
    int blockSize = getMoBlockSize(n, q);

    vector<Query> sortedQueries = queries;
    sort(sortedQueries.begin(), sortedQueries.end(),
         [&](const Query& a, const Query& b) {
             return moComparator(a, b, blockSize);
         });

    vector<long long> ans(q, 0);
    long long currentSum = 0;
    int curL = 0, curR = -1;

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

    for (const Query& qry : sortedQueries) {
        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] = currentSum;
    }
    return ans;
}

// 2.3) Find the maximum frequency (mode count) in each query range.
//      Purpose:
//        - Given an array, for each query [L, R], find the highest
//          frequency of any element in that range.
//          Example: [1, 2, 2, 3] -> max frequency is 2 (because 2 appears twice).
//      Parameters:
//        - arr : the input vector of integers (0-indexed).
//        - queries : a vector of Query structs.
//      Returns:
//        - a vector<int> where answer[i] is the max frequency for the i-th query.
//      Time complexity: O((N + Q) * sqrt(N)).
//      Constraint:
//        - Values in 'arr' should be within a reasonable range (or compressed).
//      Notes:
//        - This requires two arrays: 'freq' to count each value, and
//          'freqOfFreq' to count how many values have a specific frequency.
//        - The 'maxFreq' variable is updated dynamically.
vector<int> moMaxFrequency(const vector<int>& arr, const vector<Query>& queries) {
    int n = arr.size();
    int q = queries.size();
    int blockSize = getMoBlockSize(n, q);

    vector<Query> sortedQueries = queries;
    sort(sortedQueries.begin(), sortedQueries.end(),
         [&](const Query& a, const Query& b) {
             return moComparator(a, b, blockSize);
         });

    vector<int> ans(q, 0);
    vector<int> freq(200005, 0);       // Count of each value
    vector<int> freqOfFreq(200005, 0); // Count of frequencies
    int maxFreq = 0;
    int curL = 0, curR = -1;

    auto add = [&](int pos) {
        int val = arr[pos];
        // Remove old frequency count from freqOfFreq
        freqOfFreq[freq[val]]--;
        // Increase frequency
        freq[val]++;
        // Add new frequency count
        freqOfFreq[freq[val]]++;
        maxFreq = max(maxFreq, freq[val]);
    };

    auto remove = [&](int pos) {
        int val = arr[pos];
        freqOfFreq[freq[val]]--;
        if (freq[val] == maxFreq && freqOfFreq[freq[val]] == 0) {
            // If no value has 'maxFreq' anymore, we need to decrease maxFreq.
            maxFreq--;
        }
        freq[val]--;
        freqOfFreq[freq[val]]++;
    };

    for (const Query& qry : sortedQueries) {
        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;
}

// ===================================================================
// 3) Mo's Algorithm with Point Updates (Mo with Updates)
//    This handles queries that ask about a range, but the array can
//    change between queries (point updates).
// ===================================================================

// 3.1) Count distinct elements with updates.
//      Purpose:
//        - We have an array. Some queries ask for distinct elements in [L, R].
//          Other queries ask to change the value at position 'pos' to 'newVal'.
//          We must answer all range queries after applying updates in order.
//      Parameters:
//        - arr : the initial vector of integers (will be modified internally).
//        - queries : a vector of QueryWithUpdate structs.
//                    For Mo with updates, QueryWithUpdate must have 'l', 'r', 'idx', 'time'.
//                    'time' is the number of updates that happened BEFORE this query.
//        - updates : a vector of UpdateQuery structs (the changes to apply).
//      Returns:
//        - a vector<int> where answer[i] is the distinct count for the i-th
//          query (ordered by original query index).
//      Time complexity: O((N + Q) * N^(2/3)) which is faster than standard Mo
//                       with updates. More precisely O(N^(2/3) * (N+Q)).
//      Constraint:
//        - The number of updates and queries can be up to ~1e5.
//        - Values must be compressible.
//      Notes:
//        - This is also called "3D Mo" (L, R, Time).
//        - The sorting order is: block of L, block of R, then Time.
//        - To prepare the input: create a QueryWithUpdate for each range query.
//          Set 'idx' to its order. Set 'l' to L, 'r' to R, and 'time' to the
//          number of updates that have occurred before this query.
struct QueryWithUpdate {
    int l, r, idx, time; // time = number of updates before this query.
};

vector<int> moDistinctWithUpdates(vector<int>& arr,
                                  const vector<QueryWithUpdate>& queries,
                                  const vector<UpdateQuery>& updates) {
    int n = arr.size();
    int q = queries.size();
    int u = updates.size();

    int blockSize = pow(n, 2.0 / 3.0);
    if (blockSize < 1) blockSize = 1;

    vector<QueryWithUpdate> sortedQueries = queries;
    sort(sortedQueries.begin(), sortedQueries.end(),
         [&](const QueryWithUpdate& a, const QueryWithUpdate& b) {
             int blockL_a = a.l / blockSize;
             int blockL_b = b.l / blockSize;
             if (blockL_a != blockL_b) return blockL_a < blockL_b;

             int blockR_a = a.r / blockSize;
             int blockR_b = b.r / blockSize;
             if (blockR_a != blockR_b) return blockR_a < blockR_b;

             return a.time < b.time;
         });

    vector<int> ans(q, 0);
    vector<int> freq(200005, 0);
    int distinctCount = 0;
    int curL = 0, curR = -1, curTime = 0;

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

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

    // Applies an update (forward or backward in time)
    auto applyUpdate = [&](int time, bool forward) {
        if (forward) {
            // Apply updates[time] to arr
            int pos = updates[time].pos;
            int oldVal = updates[time].oldVal;
            int newVal = updates[time].newVal;

            if (curL <= pos && pos <= curR) {
                // If this position is inside the current range, adjust counts
                freq[oldVal]--;
                if (freq[oldVal] == 0) distinctCount--;
                if (freq[newVal] == 0) distinctCount++;
                freq[newVal]++;
            }
            arr[pos] = newVal;
        } else {
            // Revert updates[time]
            int pos = updates[time].pos;
            int oldVal = updates[time].oldVal;
            int newVal = updates[time].newVal; // current value

            if (curL <= pos && pos <= curR) {
                freq[newVal]--;
                if (freq[newVal] == 0) distinctCount--;
                if (freq[oldVal] == 0) distinctCount++;
                freq[oldVal]++;
            }
            arr[pos] = oldVal;
        }
    };

    for (const QueryWithUpdate& qry : sortedQueries) {
        // Adjust L, 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--);

        // Adjust Time pointers
        while (curTime < qry.time) {
            applyUpdate(curTime, true);
            curTime++;
        }
        while (curTime > qry.time) {
            curTime--;
            applyUpdate(curTime, false);
        }

        ans[qry.idx] = distinctCount;
    }
    return ans;
}
// ===================================================================

// ===================================================================
// 4) Mo's Algorithm on Trees
//    This answers path queries on a tree.
//    Example: "Count distinct values on the path from node U to node V".
// ===================================================================

// 4.1) Flatten a tree into an Euler tour array for Mo's algorithm.
//      Purpose:
//        - To use Mo's algorithm on a tree, we first flatten it into
//          an array of length 2*N.
//        - This helper function builds that array and provides the
//          entry (tin) and exit (tout) times for each node.
//      Parameters:
//        - adj : adjacency list of the tree (vector<vector<int>>).
//        - root : the root node of the tree (usually 0).
//      Returns:
//        - a tuple containing:
//            euler : vector<int> of length 2*N (node labels).
//            tin : vector<int> where tin[u] is the first occurrence index.
//            tout : vector<int> where tout[u] is the second occurrence index.
//      Time complexity: O(N)
//      Constraint: The graph must be a tree (no cycles).
//      Notes:
//        - We add a node to 'euler' when we enter it, and again when we exit.
tuple<vector<int>, vector<int>, vector<int>> flattenTreeForMo(const vector<vector<int>>& adj, int root) {
    int n = adj.size();
    vector<int> euler;
    euler.reserve(2 * n);
    vector<int> tin(n, 0), tout(n, 0);
    int timer = 0;

    function<void(int, int)> dfs = [&](int u, int p) {
        tin[u] = timer++;
        euler.push_back(u);
        for (int v : adj[u]) {
            if (v == p) continue;
            dfs(v, u);
        }
        tout[u] = timer++;
        euler.push_back(u);
    };

    dfs(root, -1);
    return {euler, tin, tout};
}

// 4.2) Answer path queries on a tree (e.g., distinct nodes on path).
//      Purpose:
//        - Given a tree, answer queries asking for the number of distinct
//          values on the path between node 'U' and node 'V'.
//      Parameters:
//        - nodeValues : the value of each node (vector<int> of size N).
//        - euler : the flattened array from flattenTreeForMo().
//        - tin, tout : the tin/tout arrays from flattenTreeForMo().
//        - pathQueries : a vector of pairs (u, v) representing path queries.
//        - getLCA : a function that returns the LCA of two nodes.
//                   (You must provide one, e.g., binary lifting).
//      Returns:
//        - a vector<int> where answer[i] is the distinct count on the path.
//      Time complexity: O((N + Q) * sqrt(N) + Q * log(N)) for LCA.
//      Constraint:
//        - Node values must be compressible.
//        - The LCA function must be correct.
//      Notes (IMPORTANT on how to use this):
//        - Step 1: Run flattenTreeForMo() to get 'euler', 'tin', 'tout'.
//        - Step 2: For each path query (u, v), the function builds a range
//          on the Euler array and handles LCA inclusion automatically.
vector<int> moOnTreeDistinct(const vector<int>& nodeValues,
                             const vector<int>& euler,
                             const vector<int>& tin,
                             const vector<int>& tout,
                             const vector<pair<int,int>>& pathQueries,
                             function<int(int,int)> getLCA) {
    int n = nodeValues.size();
    int q = pathQueries.size();
    int m = euler.size(); // = 2*n

    // Build regular queries for Mo on the Euler array
    vector<Query> queries(q);
    vector<int> lcaNode(q);
    vector<int> leftNode(q);      // the node with smaller tin after swapping
    vector<bool> includeLca(q);   // whether the LCA is already included in the range

    for (int i = 0; i < q; i++) {
        int u = pathQueries[i].first;
        int v = pathQueries[i].second;
        if (tin[u] > tin[v]) swap(u, v);
        int w = getLCA(u, v);
        lcaNode[i] = w;
        leftNode[i] = u;
        includeLca[i] = (w == u);

        if (includeLca[i]) {
            queries[i] = {tin[u], tin[v], i};
        } else {
            queries[i] = {tout[u], tin[v], i};
        }
    }

    int blockSize = getMoBlockSize(m, q);
    vector<Query> sortedQueries = queries;
    sort(sortedQueries.begin(), sortedQueries.end(),
         [&](const Query& a, const Query& b) {
             return moComparator(a, b, blockSize);
         });

    vector<int> ans(q, 0);
    vector<int> freq(200005, 0); // Assumes node values are < 200k
    vector<bool> vis(n, false);
    int distinctCount = 0;
    int curL = 0, curR = -1;

    auto toggle = [&](int node) {
        int val = nodeValues[node];
        if (vis[node]) {
            // Remove
            freq[val]--;
            if (freq[val] == 0) distinctCount--;
        } else {
            // Add
            if (freq[val] == 0) distinctCount++;
            freq[val]++;
        }
        vis[node] = !vis[node];
    };

    for (const Query& qry : sortedQueries) {
        while (curL > qry.l) {
            curL--;
            toggle(euler[curL]);
        }
        while (curR < qry.r) {
            curR++;
            toggle(euler[curR]);
        }
        while (curL < qry.l) {
            toggle(euler[curL]);
            curL++;
        }
        while (curR > qry.r) {
            toggle(euler[curR]);
            curR--;
        }

        // Add LCA if it is not already included in the range
        if (!includeLca[qry.idx]) {
            int lca = lcaNode[qry.idx];
            int val = nodeValues[lca];
            if (freq[val] == 0) distinctCount++;
            freq[val]++;
        }

        ans[qry.idx] = distinctCount;

        // Remove the temporary LCA addition
        if (!includeLca[qry.idx]) {
            int lca = lcaNode[qry.idx];
            int val = nodeValues[lca];
            freq[val]--;
            if (freq[val] == 0) distinctCount--;
        }
    }

    return ans;
}

// ===================================================================
// 5) Advanced Tricks & Helpers
// ===================================================================

// 5.1) Hilbert Order Sorting (an alternative to block sorting).
//      Purpose:
//        - Hilbert order is a way to sort queries that often reduces
//          pointer movement even more than the standard sqrt block sort.
//      Parameters:
//        - x, y : the L and R of the query.
//        - pow2 : a power of 2 greater than the maximum coordinate (N).
//        - rot : rotation (usually 0).
//      Returns:
//        - a 64-bit integer representing the Hilbert order key.
//      Time complexity: O(log N)
//      Notes:
//        - You can use this as a comparator instead of moComparator.
//          If you use this, you don't need the block size.
//        - It is considered an "advanced trick" and is useful for
//          performance-critical problems.
long long hilbertOrder(int x, int y, int pow2, int rot) {
    if (pow2 == 0) return 0;
    int hpow = pow2 >> 1;
    int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);
    seg = (seg + rot) & 3;
    static const int rotateDelta[4] = {3, 0, 0, 1};
    int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
    int nrot = (rot + rotateDelta[seg]) & 3;
    long long subSquareSize = 1LL << (2 * (pow2 - 1));
    long long ans = seg * subSquareSize;
    long long add = hilbertOrder(nx, ny, hpow, nrot);
    ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
    return ans;
}

// ===================================================================
// 6) Extra Utility: Mex (Minimum Excluded) in a range using Mo.
//    Finds the smallest non-negative integer missing from a range.
// ===================================================================

// 6.1) Find the Mex (Minimum EXcluded) for each query range.
//      Purpose:
//        - For each query [L, R], find the smallest non-negative integer
//          that does NOT appear in arr[L..R].
//        - Example: [0, 1, 3] -> Mex is 2. [1, 2, 3] -> Mex is 0.
//      Parameters:
//        - arr : vector of non-negative integers (0-indexed).
//        - queries : vector of Query structs.
//      Returns:
//        - vector<int> where ans[i] is the Mex for the i-th query.
//      Time complexity: O((N + Q) * sqrt(N)).
//      Constraint:
//        - arr values must be >= 0.
//      Notes:
//        - Mex is at most N (size of array).
//        - We maintain a 'freq' array and a block decomposition on values
//          to answer Mex in O(sqrt(N)) per query.
vector<int> moMex(const vector<int>& arr, const vector<Query>& queries) {
    int n = arr.size();
    int q = queries.size();
    int blockSize = getMoBlockSize(n, q);

    vector<Query> sortedQueries = queries;
    sort(sortedQueries.begin(), sortedQueries.end(),
         [&](const Query& a, const Query& b) {
             return moComparator(a, b, blockSize);
         });

    vector<int> ans(q, 0);
    // freq for values. Mex can be up to n (since only n elements).
    vector<int> freq(n + 2, 0);
    // Decomposition on the values to find Mex in O(sqrt(N)).
    int valBlockSize = max(1, (int)sqrt(n) + 1);
    vector<int> valBlockFreq((n + 2) / valBlockSize + 2, 0);

    auto add = [&](int pos) {
        int val = arr[pos];
        if (val > n) return; // ignore values bigger than n, they don't affect Mex.
        if (freq[val] == 0) valBlockFreq[val / valBlockSize]++;
        freq[val]++;
    };

    auto remove = [&](int pos) {
        int val = arr[pos];
        if (val > n) return;
        freq[val]--;
        if (freq[val] == 0) valBlockFreq[val / valBlockSize]--;
    };

    auto getMex = [&]() {
        // Find the first block that has a missing number.
        for (int b = 0; b < (int)valBlockFreq.size(); b++) {
            if (valBlockFreq[b] < valBlockSize) {
                // Inside this block, find the missing number.
                int start = b * valBlockSize;
                for (int i = start; i < start + valBlockSize; i++) {
                    if (freq[i] == 0) return i;
                }
            }
        }
        return n + 1; // Should never happen.
    };

    int curL = 0, curR = -1;
    for (const Query& qry : sortedQueries) {
        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] = getMex();
    }
    return ans;
}

// ===================================================================
// 7) Important Note on Coordinate Compression
//    If your array contains large numbers (e.g., up to 1e9), you must
//    compress them before using functions that rely on a frequency array.
//    Here is a helper to do that.
// ===================================================================

// 7.1) Compress an array of values to 0..M-1.
//      Purpose:
//        - Maps large values to small indices so we can use frequency arrays.
//      Parameters:
//        - arr : vector of integers (will be copied and modified).
//      Returns:
//        - a new vector where each value is replaced by its rank (0-based).
//      Time complexity: O(N log N)
//      Constraint: none.
//      Notes: This preserves the relative order. Equal values get the same rank.
vector<int> compressArray(const vector<int>& arr) {
    vector<int> sorted = arr;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    vector<int> res(arr.size());
    for (int i = 0; i < (int)arr.size(); i++) {
        res[i] = lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin();
    }
    return res;
}

// ===================================================================
// main() with example usage (you can ignore this part)
// ===================================================================

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

    // Example 1: Distinct elements in range
    vector<int> arr = {1, 2, 1, 3, 2, 4};
    vector<Query> queries = {
        {0, 3, 0}, // [1,2,1,3] -> distinct = 3
        {1, 4, 1}, // [2,1,3,2] -> distinct = 3
        {2, 5, 2}  // [1,3,2,4] -> distinct = 4
    };
    vector<int> distinctAns = moDistinctElements(arr, queries);
    for (int i = 0; i < (int)distinctAns.size(); i++) {
        cout << "Query " << i << ": " << distinctAns[i] << "\n";
    }

    // Example 2: Mex in range
    vector<int> arr2 = {0, 1, 2, 3, 0, 1};
    vector<Query> queries2 = {
        {0, 2, 0}, // [0,1,2] -> Mex = 3
        {1, 3, 1}, // [1,2,3] -> Mex = 0
        {2, 5, 2}  // [2,3,0,1] -> Mex = 4
    };
    vector<int> mexAns = moMex(arr2, queries2);
    cout << "\nMex results:\n";
    for (int i = 0; i < (int)mexAns.size(); i++) {
        cout << "Query " << i << ": " << mexAns[i] << "\n";
    }

    // Example 3: Max Frequency
    vector<int> arr3 = {1, 2, 2, 3, 3, 3, 4};
    vector<Query> queries3 = {
        {0, 6, 0},
        {1, 3, 1},
        {2, 4, 2}
    };
    vector<int> freqAns = moMaxFrequency(arr3, queries3);
    cout << "\nMax Frequency:\n";
    for (int x : freqAns) cout << x << " ";
    cout << "\n";

    return 0;
}