// 演算法:用 unordered_map 把「值 → 該值出現的所有下標」分組,再對每組用
// 前綴和掃一遍,每個位置 O(1) 取得答案。時間與空間皆為 O(n) 平均。
// Algorithm: bucket indices by value with an unordered_map, then sweep each
// bucket once using a running leftSum. Average O(n) time and space.

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    // LeetCode 要求成員函式名為 distance,回傳 vector<long long>
    // LeetCode requires a member function named distance returning vector<long long>.
    vector<long long> distance(vector<int>& nums) {
        int n = (int)nums.size();                // 陣列長度 / problem size
        vector<long long> ans(n, 0);             // 預設 0,單元素組就是正確答案 / defaults cover size-1 groups

        // unordered_map<int, vector<int>>:鍵是 nums 的值,值是它出現過的下標列表
        // Hash map from a value in nums to the list of indices where it appears.
        unordered_map<int, vector<int>> groups;
        groups.reserve(n);                       // 預留桶數,減少重新雜湊 / avoid rehashing as we insert

        // 一次掃過 nums,把下標 i 推到對應值的 vector 尾端 / one pass to bucket indices
        for (int i = 0; i < n; i++) {
            groups[nums[i]].push_back(i);        // 若 key 不存在會自動新建空 vector / default-inserts empty vector
        }

        // Range-for 搭配結構化綁定:直接把 pair<const int, vector<int>> 拆成 (val, idxs)
        // auto& 代表取參考(不拷貝),我們只讀不改,其實用 const auto& 也可以
        // Range-for with structured bindings unpacks each map entry into named vars;
        // auto& avoids copying the vector inside each entry.
        for (auto& [val, idxs] : groups) {
            (void)val;                           // 我們用不到 val 本身,只需要下標列表 / val unused; suppress warning
            int k = (int)idxs.size();            // 本組元素個數 / size of this bucket

            // idxs 內的下標本來就是遞增的(我們按照 i 從 0 到 n-1 推入)
            // Indices inside idxs are already sorted because we pushed i in order.
            long long total = 0;
            for (int x : idxs) total += x;       // 計算整組下標總和 / sum of all indices in this bucket

            long long leftSum = 0;               // 位置 m 左邊所有下標之和 / running sum of earlier indices
            for (int m = 0; m < k; m++) {
                long long pm = idxs[m];                                  // 目前元素的原下標 / current index
                long long rightSum = total - leftSum - pm;               // 右邊之和 = 全部 - 左邊 - 自己 / right sum
                long long left  = (long long)m * pm - leftSum;           // 左邊距離和 / distance sum to the left
                long long right = rightSum - (long long)(k - 1 - m) * pm;// 右邊距離和 / distance sum to the right
                ans[idxs[m]] = left + right;                             // 寫回答案 / write answer to original slot
                leftSum += pm;                                           // 併入 leftSum,給下一個 m 使用 / update rolling sum
            }
        }

        return ans;   // 回傳答案 vector / return the answer vector
    }
};