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

// ===================================================================
// This file contains a collection of Coordinate Compression algorithms.
// 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
// ===================================================================

// ===================================================================
// WHAT IS COORDINATE COMPRESSION?
// ===================================================================
// Coordinate compression is a technique that maps large/sparse values
// (like 10^9, 10^12) to small consecutive integers (0, 1, 2, ...).
// This is useful when:
//   - Values are too large to use as array indices
//   - We only care about the relative order of values, not their actual values
//   - We want to use frequency arrays / Fenwick trees / segment trees
//
// Example:
//   Original: [1000, 1, 1000, 500, 1]
//   Compressed: [2, 0, 2, 1, 0]
//   Now values are in range [0, 2] and can be used as array indices.
// ===================================================================

// ===================================================================
// 1) Basic Coordinate Compression
//    These are the core functions for mapping values to ranks.
// ===================================================================

// 1.1) Compress a vector of values to ranks starting from 0.
//      PURPOSE:
//        - Takes a vector of values (integers) and replaces each value
//          with its rank (0-based) based on sorted order.
//      INPUT:
//        - arr: vector of integers (will be modified in-place)
//      OUTPUT:
//        - The same vector 'arr' is modified to contain ranks.
//        - Does NOT return anything (void).
//      TIME COMPLEXITY:
//        - O(n log n) where n = arr.size() (due to sorting).
//      CONSTRAINTS:
//        - Works for any integers (positive, negative, zero).
//        - If arr is empty, does nothing.
//      NOTES:
//        - Equal values get the SAME rank.
//        - Ranks are 0-based (smallest value → 0).
//        - Example: [10, 20, 10, 30] → [0, 1, 0, 2]
void compressVector(vector<int>& arr) {
    int n = arr.size();
    if (n == 0) return;
    
    vector<int> sorted = arr;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    
    for (int i = 0; i < n; i++) {
        arr[i] = lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin();
    }
}

// 1.2) Compress a vector but return the compressed version and the mapping.
//      PURPOSE:
//        - Creates a compressed copy of the input vector.
//        - Also returns the mapping from original value → compressed rank.
//      INPUT:
//        - arr: const vector of integers (original values, not modified)
//      OUTPUT:
//        - Returns a pair:
//          - first: vector<int> containing the compressed ranks
//          - second: vector<int> containing the unique values in sorted order
//      TIME COMPLEXITY:
//        - O(n log n)
//      CONSTRAINTS:
//        - Works for any integers.
//      NOTES:
//        - To get the original value from a rank: mapping[rank]
//        - Example: arr = [100, 200, 100, 300]
//          returns: compressed = [0,1,0,2], mapping = [100,200,300]
pair<vector<int>, vector<int>> compressWithMapping(const vector<int>& arr) {
    vector<int> sorted = arr;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    
    vector<int> compressed(arr.size());
    for (int i = 0; i < (int)arr.size(); i++) {
        compressed[i] = lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin();
    }
    return {compressed, sorted};
}

// 1.3) Get the rank of a single value in a given sorted unique array.
//      PURPOSE:
//        - Given a sorted vector of unique values, find the rank of a value.
//        - This is useful when you already have the mapping from previous compression.
//      INPUT:
//        - mapping: sorted vector of unique values (must be sorted)
//        - value: the value to find the rank of
//      OUTPUT:
//        - Returns the rank (0-based) if the value exists.
//        - Returns -1 if the value is not found.
//      TIME COMPLEXITY:
//        - O(log n) using binary search.
//      CONSTRAINTS:
//        - mapping MUST be sorted.
//        - mapping should contain unique values (no duplicates).
int getRank(const vector<int>& mapping, int value) {
    auto it = lower_bound(mapping.begin(), mapping.end(), value);
    if (it != mapping.end() && *it == value) {
        return it - mapping.begin();
    }
    return -1;
}

// ===================================================================
// 2) Coordinate Compression for Arrays Used in Frequency Counting
//    These functions are useful when you need to count frequencies
//    of values that are too large to use as array indices directly.
// ===================================================================

// 2.1) Compress and count frequencies in one step.
//      PURPOSE:
//        - Compresses the array values and counts how many times each rank appears.
//      INPUT:
//        - arr: vector of integers (will be modified to compressed ranks)
//      OUTPUT:
//        - Returns a vector<int> where freq[i] = number of times rank i appears.
//        - Also modifies arr to contain compressed ranks.
//      TIME COMPLEXITY:
//        - O(n log n)
//      CONSTRAINTS:
//        - Works for any integers.
//      NOTES:
//        - After calling this function:
//          - arr contains ranks (0, 1, 2, ...)
//          - freq.size() = number of distinct values
//          - The original values are lost (arr is modified).
vector<int> compressAndCount(vector<int>& arr) {
    vector<int> sorted = arr;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    
    for (int i = 0; i < (int)arr.size(); i++) {
        arr[i] = lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin();
    }
    
    vector<int> freq(sorted.size(), 0);
    for (int x : arr) {
        freq[x]++;
    }
    return freq;
}

// 2.2) Get frequency of values in a range using compressed coordinates.
//      PURPOSE:
//        - Counts how many values in the array fall within [L, R] (inclusive).
//        - Uses coordinate compression to handle large values.
//      INPUT:
//        - arr: vector of integers (original values, not modified)
//        - L, R: the inclusive range [L, R] of values to count
//      OUTPUT:
//        - Returns the count of elements in arr that satisfy L <= value <= R.
//      TIME COMPLEXITY:
//        - O(n log n) for preprocessing + O(log n) per query.
//        - If called multiple times, you can preprocess once and query many times.
//      CONSTRAINTS:
//        - Works for any integers.
//      NOTES:
//        - This function sorts arr internally (makes a copy).
//        - For multiple queries, it's better to use a Fenwick tree or segment tree.
int countInRange(vector<int>& arr, int L, int R) {
    vector<int> sorted = arr;
    sort(sorted.begin(), sorted.end());
    int left = lower_bound(sorted.begin(), sorted.end(), L) - sorted.begin();
    int right = upper_bound(sorted.begin(), sorted.end(), R) - sorted.begin();
    return right - left;
}

// ===================================================================
// 3) Coordinate Compression for 2D Points / Grids
//    Useful for problems involving points on a plane.
// ===================================================================

// 3.1) Compress both X and Y coordinates of a set of points.
//      PURPOSE:
//        - Takes a list of points (x, y) and compresses both coordinates.
//        - This is useful for grid problems where coordinates are large.
//      INPUT:
//        - points: vector of pairs (x, y) - original coordinates
//      OUTPUT:
//        - Returns a vector of pairs where both x and y are compressed ranks.
//        - Also returns the mapping for x and y coordinates separately.
//      TIME COMPLEXITY:
//        - O(n log n)
//      CONSTRAINTS:
//        - Works for any integers.
//      NOTES:
//        - Points are compressed independently (x and y separate).
//        - Example: [(100,200), (100,300), (500,200)]
//          returns: [(0,0), (0,1), (1,0)]
tuple<vector<pair<int,int>>, vector<int>, vector<int>> compress2DPoints(
    const vector<pair<int,int>>& points
) {
    vector<int> xs, ys;
    for (auto& p : points) {
        xs.push_back(p.first);
        ys.push_back(p.second);
    }
    
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    
    vector<pair<int,int>> compressed;
    for (auto& p : points) {
        int cx = lower_bound(xs.begin(), xs.end(), p.first) - xs.begin();
        int cy = lower_bound(ys.begin(), ys.end(), p.second) - ys.begin();
        compressed.push_back({cx, cy});
    }
    
    return {compressed, xs, ys};
}

// ===================================================================
// 4) Coordinate Compression for Fenwick Tree / Segment Tree
//    These functions prepare data for range query data structures.
// ===================================================================

// 4.1) Prepare a frequency array for Fenwick tree with compressed coordinates.
//      PURPOSE:
//        - Compresses values and creates a frequency array that can be used
//          with a Fenwick tree (Binary Indexed Tree) for prefix sum queries.
//      INPUT:
//        - arr: vector of integers (original values)
//      OUTPUT:
//        - Returns a vector<int> freq where freq[i] = count of value with rank i.
//        - The compressed values can then be used as indices in a Fenwick tree.
//      TIME COMPLEXITY:
//        - O(n log n)
//      CONSTRAINTS:
//        - Works for any integers.
//      NOTES:
//        - This is just a helper; you still need to build the Fenwick tree.
//        - Example: arr = [10, 20, 10, 30, 20]
//          returns: freq = [2, 2, 1] (ranks: 10→0, 20→1, 30→2)
vector<int> prepareFenwickFreq(const vector<int>& arr) {
    vector<int> sorted = arr;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    
    vector<int> freq(sorted.size(), 0);
    for (int x : arr) {
        int rank = lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
        freq[rank]++;
    }
    return freq;
}

// 4.2) Get compressed indices for a Fenwick tree with optional offset.
//      PURPOSE:
//        - Compresses values and optionally shifts them to start from 1.
//        - Fenwick trees typically use 1-based indexing.
//      INPUT:
//        - arr: vector of integers (original values)
//        - oneBased: if true, ranks start from 1 instead of 0
//      OUTPUT:
//        - Returns a vector<int> containing compressed ranks.
//        - If oneBased is true, ranks are 1, 2, 3, ... (not 0, 1, 2, ...)
//      TIME COMPLEXITY:
//        - O(n log n)
//      CONSTRAINTS:
//        - Works for any integers.
//      NOTES:
//        - Use oneBased=true when the compressed values will be used as
//          indices in a Fenwick tree (which is 1-indexed).
vector<int> compressForFenwick(const vector<int>& arr, bool oneBased = true) {
    vector<int> sorted = arr;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    
    vector<int> result(arr.size());
    for (int i = 0; i < (int)arr.size(); i++) {
        int rank = lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin();
        result[i] = rank + (oneBased ? 1 : 0);
    }
    return result;
}

// ===================================================================
// 5) Advanced Techniques: Using Compression for "Difference Array"
//    on large coordinate ranges (sweep line).
// ===================================================================

// 5.1) Sweep line with coordinate compression for range updates.
//      PURPOSE:
//        - Given a list of range updates [L, R] with a value to add,
//          compute the final values at compressed coordinates.
//        - This is useful when coordinates are large and sparse.
//      INPUT:
//        - updates: vector of triples (L, R, val) where:
//          - L: left endpoint (inclusive)
//          - R: right endpoint (inclusive)
//          - val: value to add to all positions in [L, R]
//      OUTPUT:
//        - Returns a vector of pairs (coordinate, accumulated_value)
//          for each unique coordinate that appears in any update.
//      TIME COMPLEXITY:
//        - O(n log n) where n = updates.size()
//      CONSTRAINTS:
//        - Works for any integer coordinates.
//        - L <= R for each update.
//      NOTES:
//        - This is the "difference array" technique on compressed coordinates.
//        - Example: updates = [(1,5,10), (3,7,5)]
//          returns: [(1,10), (3,15), (6,5), (8,0)]
//          (meaning: from 1 to 2:10, from 3 to 5:15, from 6 to 7:5)
vector<pair<int, long long>> sweepLineCompressed(const vector<tuple<int,int,int>>& updates) {
    vector<int> coords;
    for (auto& [L, R, val] : updates) {
        coords.push_back(L);
        coords.push_back(R + 1); // R+1 marks the end of the range
    }
    
    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    
    vector<long long> diff(coords.size(), 0);
    for (auto& [L, R, val] : updates) {
        int lIdx = lower_bound(coords.begin(), coords.end(), L) - coords.begin();
        int rIdx = lower_bound(coords.begin(), coords.end(), R + 1) - coords.begin();
        diff[lIdx] += val;
        diff[rIdx] -= val;
    }
    
    vector<pair<int, long long>> result;
    long long cur = 0;
    for (int i = 0; i < (int)coords.size(); i++) {
        cur += diff[i];
        result.push_back({coords[i], cur});
    }
    return result;
}

// ===================================================================
// 6) Coordinate Compression for Offline Queries
//    Preprocessing for answering queries on compressed values.
// ===================================================================

// 6.1) Offline processing: compress all values from array and queries together.
//      PURPOSE:
//        - In many problems, queries reference values that may not exist in the array.
//        - This function compresses ALL values (from array and queries) together.
//      INPUT:
//        - arr: vector of integers (the main array)
//        - queries: vector of integers (query values to check)
//      OUTPUT:
//        - Returns a pair:
//          - first: vector<int> compressed arr
//          - second: vector<int> compressed queries
//          - Both share the same mapping (all values combined).
//      TIME COMPLEXITY:
//        - O((n+m) log (n+m)) where n=arr.size(), m=queries.size()
//      CONSTRAINTS:
//        - Works for any integers.
//      NOTES:
//        - Useful when you need to answer queries like:
//          "How many elements in arr are <= query_value?"
//        - After compression, you can use a Fenwick tree or sorting.
pair<vector<int>, vector<int>> compressWithQueries(
    const vector<int>& arr, 
    const vector<int>& queries
) {
    vector<int> allValues = arr;
    for (int x : queries) allValues.push_back(x);
    
    sort(allValues.begin(), allValues.end());
    allValues.erase(unique(allValues.begin(), allValues.end()), allValues.end());
    
    vector<int> compressedArr(arr.size());
    for (int i = 0; i < (int)arr.size(); i++) {
        compressedArr[i] = lower_bound(allValues.begin(), allValues.end(), arr[i]) - allValues.begin();
    }
    
    vector<int> compressedQueries(queries.size());
    for (int i = 0; i < (int)queries.size(); i++) {
        compressedQueries[i] = lower_bound(allValues.begin(), allValues.end(), queries[i]) - allValues.begin();
    }
    
    return {compressedArr, compressedQueries};
}

// ===================================================================
// 7) Advanced: Coordinate Compression on Pair/Tuple Values
//    For problems where you need to compress composite keys.
// ===================================================================

// 7.1) Compress a vector of pairs (tuple) to ranks.
//      PURPOSE:
//        - Compresses pairs (or tuples) based on lexicographic order.
//        - Useful when you have points (x, y) and need to assign ranks.
//      INPUT:
//        - pairs: vector of pairs (a, b) - values to compress together.
//      OUTPUT:
//        - Returns a vector<int> where each element is the rank of that pair.
//        - Equal pairs get the same rank.
//      TIME COMPLEXITY:
//        - O(n log n)
//      CONSTRAINTS:
//        - Works for any comparable types.
//      NOTES:
//        - Ranks are assigned based on sorted order of pairs.
//        - Example: [(1,2), (2,1), (1,2), (2,2)]
//          returns: [0, 1, 0, 2]
vector<int> compressPairs(const vector<pair<int,int>>& pairs) {
    vector<pair<int,int>> sorted = pairs;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    
    vector<int> result(pairs.size());
    for (int i = 0; i < (int)pairs.size(); i++) {
        result[i] = lower_bound(sorted.begin(), sorted.end(), pairs[i]) - sorted.begin();
    }
    return result;
}

// ===================================================================
// 8) Tricks & Patterns that appeared in ECPC/ACPC
//    Extra useful techniques involving coordinate compression.
// ===================================================================

// 8.1) Compress and find the number of distinct values in each subarray.
//      PURPOSE:
//        - For each subarray [L, R], count how many distinct values appear.
//        - Uses compression to handle large values.
//      INPUT:
//        - arr: vector of integers (original values)
//        - queries: vector of pairs (L, R) - 0-based indices
//      OUTPUT:
//        - Returns a vector<int> where answer[i] = number of distinct values
//          in arr[queries[i].first ... queries[i].second]
//      TIME COMPLEXITY:
//        - O((n+q) log n) using Mo's algorithm with compression.
//      CONSTRAINTS:
//        - Works for any integers.
//        - 0 <= L <= R < n
//      NOTES:
//        - This is a common pattern in ECPC problems.
//        - The function first compresses arr, then uses Mo's algorithm.
//        - Mo's algorithm is a technique for answering range queries offline.
//        - The implementation below is a naive placeholder; for actual Mo's
//          algorithm, replace the inner loop with the standard Mo's approach.
vector<int> distinctInRange(const vector<int>& arr, const vector<pair<int,int>>& queries) {
    // First compress the array
    vector<int> compressed = arr;
    compressVector(compressed);
    
    // Now use Mo's algorithm to answer queries
    // (This is a simplified placeholder - actual Mo's algorithm is more complex)
    int n = compressed.size();
    int q = queries.size();
    vector<int> freq(n, 0);   // size n is safe because ranks are in [0, distinct-1] <= n
    vector<int> answers(q, 0);
    
    // For each query, count distinct values in the range
    // This is O(n*q) for simplicity, but actual Mo's algorithm would be O((n+q)*sqrt(n))
    for (int qi = 0; qi < q; qi++) {
        int L = queries[qi].first;
        int R = queries[qi].second;
        
        fill(freq.begin(), freq.end(), 0);
        int distinct = 0;
        for (int i = L; i <= R; i++) {
            if (freq[compressed[i]] == 0) distinct++;
            freq[compressed[i]]++;
        }
        answers[qi] = distinct;
    }
    return answers;
}

// 8.2) Count subarrays with at most K distinct values using compression.
//      PURPOSE:
//        - Counts how many subarrays have at most K distinct values.
//        - Uses compression to handle large values efficiently.
//      INPUT:
//        - arr: vector of integers (original values)
//        - K: maximum number of distinct values allowed
//      OUTPUT:
//        - Returns the total number of subarrays with at most K distinct values.
//      TIME COMPLEXITY:
//        - O(n log n) for compression + O(n) for sliding window.
//      CONSTRAINTS:
//        - Works for any integers.
//        - K >= 0.
//      NOTES:
//        - This is a classic sliding window problem that requires compression.
//        - The sliding window technique: maintain a window [L, R] with <= K distinct.
//        - For each R, extend L as little as possible.
long long countSubarraysAtMostKDistinct(vector<int>& arr, int K) {
    // Compress arr to small ranks
    compressVector(arr);
    
    int n = arr.size();
    long long ans = 0;
    unordered_map<int, int> freq;
    int L = 0;
    
    for (int R = 0; R < n; R++) {
        freq[arr[R]]++;
        while ((int)freq.size() > K) {
            freq[arr[L]]--;
            if (freq[arr[L]] == 0) freq.erase(arr[L]);
            L++;
        }
        ans += (R - L + 1);
    }
    return ans;
}

// 8.3) Compress values and find the maximum frequency of any value.
//      PURPOSE:
//        - Finds the value that appears most frequently in the array.
//        - Uses compression to count frequencies efficiently.
//      INPUT:
//        - arr: vector of integers (original values, not modified)
//      OUTPUT:
//        - Returns a pair (value, frequency) where:
//          - value: the original value that appears most often
//          - frequency: how many times it appears
//        - If multiple values have the same max frequency, returns the smallest value.
//      TIME COMPLEXITY:
//        - O(n log n)
//      CONSTRAINTS:
//        - Works for any integers.
//        - arr must not be empty.
pair<int,int> maxFrequencyValue(const vector<int>& arr) {
    auto [compressed, mapping] = compressWithMapping(arr);
    vector<int> freq(mapping.size(), 0);
    for (int x : compressed) freq[x]++;
    
    int maxFreq = 0;
    int maxRank = 0;
    for (int i = 0; i < (int)freq.size(); i++) {
        if (freq[i] > maxFreq) {
            maxFreq = freq[i];
            maxRank = i;
        }
    }
    return {mapping[maxRank], maxFreq};
}

// ===================================================================
// 9) Advanced: Coordinate Compression with Coordinate "Shifting"
//    For problems where you need to maintain gaps between coordinates.
// ===================================================================

// 9.1) Compress coordinates while preserving gaps (for coordinate compression
//      with distance calculations).
//      PURPOSE:
//        - Sometimes you need to preserve the actual differences between
//          coordinates, not just their order.
//        - This function compresses values but keeps the gaps.
//      INPUT:
//        - coords: vector of integers (sorted or unsorted)
//      OUTPUT:
//        - Returns a vector of integers where each value is mapped to
//          its rank, but preserving gaps.
//      TIME COMPLEXITY:
//        - O(n log n)
//      CONSTRAINTS:
//        - Works for any integers.
//      NOTES:
//        - Example: coords = [1, 3, 10, 100]
//          returns: [0, 1, 2, 3] (no gaps preserved)
//          This is the same as regular compression.
//        - To preserve gaps, you need a different approach (not shown here).
//        - In most cases, regular compression is sufficient.
vector<int> compressPreserveGaps(vector<int>& coords) {
    // This is the same as regular compression for now.
    // Preserving gaps requires more complex mapping that tracks original differences.
    compressVector(coords);
    return coords;
}

// ===================================================================
// 10) Helper: Binary Search on Compressed Values
//     Common patterns for querying compressed data.
// ===================================================================

// 10.1) Find how many compressed values are < X.
//       PURPOSE:
//         - Counts how many elements in the array are strictly less than X.
//         - Uses compression for efficiency.
//       INPUT:
//         - arr: vector of integers (original values)
//         - X: the threshold value
//       OUTPUT:
//         - Returns the count of elements < X.
//       TIME COMPLEXITY:
//         - O(n log n) for preprocessing + O(log n) per query.
//         - If called once, O(n log n).
//       CONSTRAINTS:
//         - Works for any integers.
int countLessThan(vector<int>& arr, int X) {
    vector<int> sorted = arr;
    sort(sorted.begin(), sorted.end());
    return lower_bound(sorted.begin(), sorted.end(), X) - sorted.begin();
}

// 10.2) Find how many compressed values are in [L, R] (inclusive).
//       PURPOSE:
//         - Counts how many elements in the array are in the range [L, R].
//         - Uses compression for efficiency.
//       INPUT:
//         - arr: vector of integers (original values)
//         - L, R: inclusive range
//       OUTPUT:
//         - Returns the count of elements in [L, R].
//       TIME COMPLEXITY:
//         - O(n log n) for preprocessing + O(log n) per query.
int countInRangeSimple(vector<int>& arr, int L, int R) {
    if (L > R) return 0;
    vector<int> sorted = arr;
    sort(sorted.begin(), sorted.end());
    int left = lower_bound(sorted.begin(), sorted.end(), L) - sorted.begin();
    int right = upper_bound(sorted.begin(), sorted.end(), R) - sorted.begin();
    return right - left;
}

// ===================================================================
// 11) Common Pitfalls & Tips (Documentation only)
// ===================================================================

// ===================================================================
// PITFALL 1: Losing original values after compression.
// SOLUTION: Keep a copy of the original array, or use compressWithMapping.
//
// PITFALL 2: Using compression on negative numbers without care.
// SOLUTION: The functions work with negative numbers just fine.
//           Sorting handles negative values correctly.
//
// PITFALL 3: Not handling duplicate values correctly.
// SOLUTION: Always use 'unique()' to remove duplicates before assigning ranks.
//
// PITFALL 4: Using compressed values as indices without checking bounds.
// SOLUTION: Compressed values are always in range [0, distinct_count - 1].
//           This is safe to use as array indices.
//
// PITFALL 5: Forgetting that compression changes the array.
// SOLUTION: If you need the original values, make a copy before compressing.
// ===================================================================

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

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

    // Example 1: Basic compression
    vector<int> arr = {100, 200, 100, 300, 200, 100};
    cout << "Original: ";
    for (int x : arr) cout << x << " ";
    cout << "\n";
    
    compressVector(arr);
    cout << "Compressed: ";
    for (int x : arr) cout << x << " ";
    cout << "\n"; // Output: 0 1 0 2 1 0

    // Example 2: Compression with mapping
    vector<int> arr2 = {10, 20, 10, 30, 20};
    auto [compressed, mapping] = compressWithMapping(arr2);
    cout << "Compressed: ";
    for (int x : compressed) cout << x << " ";
    cout << "\n";
    cout << "Mapping: ";
    for (int x : mapping) cout << x << " ";
    cout << "\n";

    // Example 3: Range counting
    vector<int> arr3 = {5, 2, 8, 1, 9, 3, 7};
    cout << "Count in [3, 7]: " << countInRangeSimple(arr3, 3, 7) << "\n"; // 4

    // Example 4: Count subarrays with at most 2 distinct
    vector<int> arr4 = {1, 2, 1, 2, 3};
    cout << "Subarrays with at most 2 distinct: " 
         << countSubarraysAtMostKDistinct(arr4, 2) << "\n"; // 12

    return 0;
}