class Solution {
private:
    // 定义我们要存储的元素类型：(frequency, value)
    using Elem = pair<int, int>;

    // 自定义比较器，严格按照题目的排序规则
    // 1. 频率（frequency）降序
    // 2. 如果频率相同，则数值（value）降序
    struct Comparator {
        bool operator()(const Elem& a, const Elem& b) const {
            if (a.first != b.first) {
                return a.first > b.first;
            }
            return a.second > b.second;
        }
    };

    // `kept_set` 存储 Top x 元素
    set<Elem, Comparator> kept_set;
    // `removed_set` 存储所有其他元素
    set<Elem, Comparator> removed_set;
    // `freq_map` 跟踪窗口内每个元素的当前频率
    unordered_map<int, int> freq_map;
    
    // `x_sum` 是 kept_set 中元素的总和
    long long x_sum = 0;
    // `total_sum` 是整个窗口所有元素的总和
    long long total_sum = 0;
    
    // 存储 x 的值
    int x_val;
    // 实例化比较器
    Comparator comp;

    /**
     * @brief 更新元素的频率和其在两个 set 中的位置。
     * @param val 要更新的元素值。
     * @param old_freq 更新前的频率。
     * @param new_freq 更新后的频率。
     */
    void update_sets(int val, int old_freq, int new_freq) {
        // 1. 如果旧频率 > 0，说明该元素已存在，需要先移除旧条目
        if (old_freq > 0) {
            Elem old_elem = {old_freq, val};
            // 检查它在哪个 set 中
            if (kept_set.count(old_elem)) {
                kept_set.erase(old_elem);
                // 如果它在 kept_set 中，需要从 x_sum 中减去它的贡献
                x_sum -= (long long)old_freq * val;
            } else {
                removed_set.erase(old_elem);
            }
        }

        // 2. 如果新频率 > 0，说明元素仍然存在，需要添加新条目
        if (new_freq > 0) {
            Elem new_elem = {new_freq, val};
            // *重要*：我们总是先将其添加到 removed_set。
            // 稍后的 balance() 函数会决定它是否应该被移到 kept_set。
            removed_set.insert(new_elem);
        }
    }

    /**
     * @brief 重新平衡 kept_set 和 removed_set。
     * 确保 kept_set 包含的
     * 始终是当前窗口中“最好”的 x 个元素。
     */
    void balance() {
        // 1. 如果 kept_set 不足 x 个，从 removed_set 移动最好的元素过来
        while (kept_set.size() < x_val && !removed_set.empty()) {
            Elem to_move = *removed_set.begin();
            removed_set.erase(removed_set.begin());
            kept_set.insert(to_move);
            // 增加它对 x_sum 的贡献
            x_sum += (long long)to_move.first * to_move.second;
        }

        // 2. 如果 kept_set 超过 x 个，移动最差的元素到 removed_set
        while (kept_set.size() > x_val) {
            // .rbegin() 指向最后一个（即最差的）元素
            Elem to_move = *kept_set.rbegin(); 
            // C++ set 擦除末尾元素的标准方法
            kept_set.erase(std::prev(kept_set.end())); 
            removed_set.insert(to_move);
            // 减去它对 x_sum 的贡献
            x_sum -= (long long)to_move.first * to_move.second;
        }

        // 3. 交换：如果 removed_set 中最好的元素 > kept_set 中最差的元素
        //    *comp(a, b)* 返回 true 意味着 a "优于" b
        while (!kept_set.empty() && !removed_set.empty() && 
               comp(*removed_set.begin(), *kept_set.rbegin())) {
            
            Elem to_add = *removed_set.begin();
            Elem to_remove = *kept_set.rbegin();

            // 执行交换
            removed_set.erase(removed_set.begin());
            kept_set.erase(std::prev(kept_set.end()));
            kept_set.insert(to_add);
            removed_set.insert(to_remove);

            // 更新 x_sum
            x_sum += (long long)to_add.first * to_add.second;
            x_sum -= (long long)to_remove.first * to_remove.second;
        }
    }

public:
    vector<int> findXSum(vector<int>& nums, int k, int x) {
        int n = nums.size();
        this->x_val = x; // 存储 x
        vector<int> answer;

        // --- 优化：特殊情况 k <= x ---
        // 根据规则，如果不同元素少于 x 个，x-sum 等于总和。
        // 窗口长度为 k，不同元素 <= k。
        // 如果 k <= x，那么不同元素 <= x，因此 x-sum 总是等于窗口总和。
        if (k <= x) {
            long long current_sum = 0;
            for (int i = 0; i < n; ++i) {
                current_sum += nums[i];
                // 窗口开始滑动后，移除左侧元素
                if (i >= k) {
                    current_sum -= nums[i - k];
                }
                // 当窗口形成（即 i >= k-1）时，记录答案
                if (i >= k - 1) {
                    // 结果要求是 int，但计算过程用 long long 防止溢出
                    answer.push_back((int)current_sum);
                }
            }
            return answer;
        }

        // --- 常规情况：k > x ---

        // 1. 初始化第一个窗口 (nums[0...k-1])
        for (int i = 0; i < k; ++i) {
            freq_map[nums[i]]++;
            total_sum += nums[i];
        }

        // 将第一个窗口的频率统计放入 removed_set
        for (auto const& [val, freq] : freq_map) {
            removed_set.insert({freq, val});
        }

        // 第一次平衡，填满 kept_set
        balance();

        // 记录第一个窗口的答案
        // 规则：如果不同元素 <= x，使用 total_sum
        if (freq_map.size() <= x) {
            answer.push_back((int)total_sum);
        } else {
            answer.push_back((int)x_sum);
        }

        // 2. 开始滑动窗口
        // i 是新加入窗口的元素索引
        for (int i = k; i < n; ++i) {
            int val_to_add = nums[i];
            int val_to_remove = nums[i - k];

            // 更新总和
            total_sum = total_sum - val_to_remove + val_to_add;

            // --- 处理移除 ---
            int old_freq_rem = freq_map[val_to_remove];
            int new_freq_rem = old_freq_rem - 1;
            freq_map[val_to_remove] = new_freq_rem;
            if (new_freq_rem == 0) {
                freq_map.erase(val_to_remove); // 移除map中的键
            }
            // 更新 set
            update_sets(val_to_remove, old_freq_rem, new_freq_rem);

            // --- 处理添加 ---
            int old_freq_add = freq_map.count(val_to_add) ? freq_map[val_to_add] : 0;
            int new_freq_add = old_freq_add + 1;
            freq_map[val_to_add] = new_freq_add;
            // 更新 set
            update_sets(val_to_add, old_freq_add, new_freq_add);

            // --- 重新平衡 ---
            balance();

            // 记录当前窗口的答案
            if (freq_map.size() <= x) {
                answer.push_back((int)total_sum);
            } else {
                answer.push_back((int)x_sum);
            }
        }

        return answer;
    }
};