You are given an integer array A. Your task is to calculate the sum of absolute difference of indices of first and last occurrence for every integer that is present in array A.
Formally, if element x occurs m times in the array at indices B1, B2, B3, ...,Bm, then the answer for x will be Bm−B1 if array B is sorted.
You are required to calculate the sum of the answer for every such x that occurs in the array.
Refer to sample notes and explanations for better understanding.
Input format
- The first line contains an integer T that denotes the number of test cases.
- The first line of each test case contains an integer x that denotes the number of elements in the array.
- The second line of each test case contains x space seperated integers A1, A2, A3, ...,An.
Output format
For each test case, print a single line as described in the problem statement.
Constraints
1≤T≤1000
1≤N≤200000
1≤Ai≤1e9∀i∈[0,n−1]
The sum of N over all test cases will not exceed 200000.
The elements which occur in the array are 1,2,3.
Let us consider 1 it has only one occurence so answer for 1 is 0.
Let us consider 2 it has two occurence at 2 and 5 so |5-2|=3
Let us consider 3 it has two occurence at 3 and 4 so |4-3|=1.
So total sum=0+3+1=4.
If there are more than two occrence we only need to consider the first and last.
