Question

Problem Statement

We define “frequency factor” P, of an array X, as:

P = ∑ f(k) ∗ [ f(k) − 1 ] MAX

k=1

Here MAX denotes the maximum element of the array and f(k) denotes the frequency of the element with value equal to k present in the array.

For Example, X = [ 1, 2, 1, 2], MAX = 2, f(1) = 2, f(2) = 2

P = f(1) ∗ [ f(1) − 1 ] + f(2) ∗ [ f(2) − 1 ] = 2 + 2 = 4

You are given an array A, of N integers, find the sum of “frequency factor” of all the subarrays of A.

Subarray is a contiguous part of array formed by deleting some (possibly none) elements from start and end of the array.

You are given T independent test cases.

Constraints

• 1 <= T <= 10 • 1 <= N <= 10^5 • 1 <= Ai <= 10^9 • All input values are integers.

Input Format

• First-line contains T. • First line of each test case consists of a single integer N. • Second line of each test case consists of N space separated integers A1, A2, ..., AN

Output Format

• Print in a newline for each test case a single integer denoting the sum of “frequency factor” of all the subarrays of A.

Sample Input 1

2 3

1 1 1 5 1 2 3 4 5

Sample Output 1

10 0

Explanation of Sample 1

For 1st test case, There are three subarrays of type [ 1], P1 = 0 There are two subarrays of type [1,1], P2 = 4 There is one subarray of type [ 1,1 ,1], P3 = 6 Sum of “frequency factor” = 0 + 4 + 6 = 10

Answer 1

Answer:

I don't know what it its answer