B'This is the hard version of the problem. The only difference is that in this version, a_i <= 10^9 . For a given sequence of n integers a , a triple (i, j, k) is called magic if: Kolya received a sequence of integers a as a gift and now wants to count the number of magic triples for it. Help him with this task! Note that there are no constraints on the order of integers i , j and k . The first line contains a single integer t ( 1 <= t <= 10^4 ) -- the number of test cases. The description of the test cases follows. The first line of the test case contains a single integer n ( 3 <= n <= 2 cdot 10^5 ) -- the length of the sequence. The second line of the test contains n integers a_1, a_2, a_3, ... , a_n ( 1 <= a_i <= 10^9 ) -- the elements of the sequence a . The sum of n over all test cases does not exceed 2 cdot 10^5 . For each test case, output a single integer -- the number of magic triples for the sequence a . In the first example, there are 6 magic triples for the sequence a -- (2, 3, 5) , (2, 5, 3) , (3, 2, 5) , (3, 5, 2) , (5, 2, 3) , (5, 3, 2) . In the second example, there is a single magic triple for the sequence a -- (2, 1, 3) . '...