You are given a 0-indexed array of n integers arr.

The interval between two elements in arr is defined as the absolute difference between their indices. More formally, the interval between arr[i] and arr[j] is |i - j|.

Return an array intervals of length n where intervals[i] is the sum of intervals between arr[i] and each element in arr with the same value as arr[i].

Note: |x| is the absolute value of x.

&nbsp;
Example 1:

Input: arr = [2,1,3,1,2,3,3]
Output: [4,2,7,2,4,4,5]
Explanation:
- Index 0: Another 2 is found at index 4. |0 - 4| = 4
- Index 1: Another 1 is found at index 3. |1 - 3| = 2
- Index 2: Two more 3s are found at indices 5 and 6. |2 - 5| + |2 - 6| = 7
- Index 3: Another 1 is found at index 1. |3 - 1| = 2
- Index 4: Another 2 is found at index 0. |4 - 0| = 4
- Index 5: Two more 3s are found at indices 2 and 6. |5 - 2| + |5 - 6| = 4
- Index 6: Two more 3s are found at indices 2 and 5. |6 - 2| + |6 - 5| = 5


Example 2:

Input: arr = [10,5,10,10]
Output: [5,0,3,4]
Explanation:
- Index 0: Two more 10s are found at indices 2 and 3. |0 - 2| + |0 - 3| = 5
- Index 1: There is only one 5 in the array, so its sum of intervals to identical elements is 0.
- Index 2: Two more 10s are found at indices 0 and 3. |2 - 0| + |2 - 3| = 3
- Index 3: Two more 10s are found at indices 0 and 2. |3 - 0| + |3 - 2| = 4


&nbsp;
Constraints:


	n == arr.length
	1 &lt;= n &lt;= 105
	1 &lt;= arr[i] &lt;= 105


# helper data structure Scout
class Scout:
    
    def __init__(self, prev_idx=-1, count_of_equal=0):
        
        # record of index of last identical element
        self.prev_idx = prev_idx
        
        # count of identical elements so far
        self.count_of_equal = count_of_equal
    
    def __iter__(self):
		# ouput previous index, and count of equal in order
        return iter( (self.prev_idx, self.count_of_equal) )
    
    
        
class Solution:
    def getDistances(self, arr: List[int]) -> List[int]:
        
        size = len(arr)
        
        pre_scout = defaultdict( Scout )
        pre_dist_sum = [0 for _ in range(size)]
        
        post_scout = defaultdict( Scout )
        post_dist_sum = [0 for _ in range(size)]
        
        
        ## Step_1:
        # update for pre_dist_sum table, direction is from left to right
        for i, element in enumerate(arr):
            
            prev_equal_idx, prev_count_of_equal = pre_scout[element]
            
            # update pre_dist_sum table if we have identical elements before index i
            if prev_count_of_equal:
                pre_dist_sum[i] += pre_dist_sum[ prev_equal_idx ] + (i - prev_equal_idx) * prev_count_of_equal
            
            # update Scout information for current element
            pre_scout[element] = i, prev_count_of_equal+1
            
        # --------------------------------------------------------------
        
        ## Step_2:
        # update for pos_dist_sum table, direction is from right to left
        for i, element in reversed( [*enumerate(arr)] ):
            
            post_equal_idx, post_count_of_equal = post_scout[element]

            # update post_dist_sum table if we have identical elements after index i
            if post_count_of_equal:
                post_dist_sum[i] += post_dist_sum[ post_equal_idx ] + (post_equal_idx - i) * post_count_of_equal
            
            # update Scout information for current element
            post_scout[element] = i, post_count_of_equal+1
            
            
        ## Step_3:
        # Generate final output by definition
        return [ pre_dist_sum[i] + post_dist_sum[i] for i in range(size) ]
        
        
class Solution {
    public long[] getDistances(int[] arr) {
        long[] output = new long[arr.length];
        Map<Integer, Long> sumMap = new HashMap<>();
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int i = 0; i < arr.length; ++ i) {
            if (!sumMap.containsKey(arr[i])) {
                sumMap.put(arr[i], 0l);
                countMap.put(arr[i], 0);
            }

            output[i] += i * (long)countMap.get(arr[i]) - sumMap.get(arr[i]);
            sumMap.put(arr[i], sumMap.get(arr[i]) + i);
            countMap.put(arr[i], countMap.get(arr[i]) + 1);
        }

        sumMap = new HashMap<>();
        countMap = new HashMap<>();
        int len = arr.length;
        for (int i = len - 1; i >= 0; -- i) {
            if (!sumMap.containsKey(arr[i])) {
                sumMap.put(arr[i], 0l);
                countMap.put(arr[i], 0);
            }

            output[i] += (len - i - 1) * (long)countMap.get(arr[i]) - sumMap.get(arr[i]);
            sumMap.put(arr[i], sumMap.get(arr[i]) + (len - i - 1));
            countMap.put(arr[i], countMap.get(arr[i]) + 1);
        }

        return output;
    }
}
class Solution {
public:
    vector<long long> getDistances(vector<int>& arr) {
        int size=arr.size();
        vector<long long>pre(size,0),suf(size,0),ans(size,0);
        unordered_map<int,vector<int>>mp;
        
        // store index of the same elements.
        for(int i=0;i<size;i++)
            mp[arr[i]].push_back(i);
       //  prefix will store the sum of absolute diff. from the starting index of current element to the current index.
        // pre[cur index]=pre[prev index]+ number of same elements before cur element * abs diff of cur element pos and pre element pos
        for(auto &p:mp){
            auto vec=p.second;
            for(int i=1;i<vec.size();i++)
                pre[vec[i]]=  pre[vec[i-1]]+  i*(long)(vec[i]-vec[i-1]);
        }
       // suffix will store the sum of absolute diff. from the ending index of current element to the current index.
        // same formula as above but in reverse order
        for(auto &p:mp){
            auto vec=p.second;
            for(int i=vec.size()-2;i>=0;i--)
                suf[vec[i]]=  suf[vec[i+1]] + long(vec.size()-1-i) * (long)(vec[i+1]-vec[i]);
        }
        for(int i=0;i<size;i++)
            ans[i]+=(pre[i]+suf[i]);
        return ans;
    }
};
var getDistances = function(arr) {
    const map = new Map();
    const result = new Array(arr.length).fill(0);

    for (let i = 0; i < arr.length; i++) {
        const num = arr[i];
        const val = map.get(num) || {
            count: 0,
            sum: 0
        };
        result[i] += (val.count * i) - val.sum;
        val.sum += i;
        val.count++;
        map.set(num, val);
    }
    map.clear();

    for (let i = arr.length - 1; i >= 0; i--) {
        const num = arr[i];
        const val = map.get(num) || {
            count: 0,
            sum: 0
        };
        result[i] += val.sum - (val.count * i);
        val.sum += i;
        val.count++;
        map.set(num, val);
    }

    return result;
};
Intervals Between Identical Elements