You are given an arrangement an of length n comprising of integers from 1 to n. The grouping may contain duplicates (for example a few components can be equal). Track down the number of tuples of m=3 components
Correct answer will be upvoted else Multiple Downvoted. Computer science.
You are given an arrangement an of length n comprising of integers from 1 to n. The grouping may contain duplicates (for example a few components can be equal).
Track down the number of tuples of m=3 components with the end goal that the maximum number in the tuple varies from the base by close to k=2. Formally, you want to view as the number of triples of lists i<j<z with the end goal that
max(
For example, on the off chance that n=4 and a=[1,2,4,3], there are two such triples (i=1,j=2,z=4 and i=2,j=3,z=4). In the event that n=4 and a=[1,1,1,1], all four potential triples are suitable.
Input
The principal line contains a solitary integer t (1≤t≤2⋅105) — the number of experiments. Then, at that point, t experiments follow.
The principal line of each experiment contains an integer n (1≤n≤2⋅105) — the length of the succession a.
The following line contains n integers a1,a2,… ,an (1≤ai≤n) — the grouping a.
It is guaranteed that the amount of n for all experiments doesn't surpass 2⋅105.
Output
Output t answers to the given experiments. Each answer is the necessary number of triples of components, to such an extent that the maximum value in the triple varies from the base by close to 2. Note that in distinction to the hard form of the issue, you don't have to output the answer by modulo. You should output the exact value of the answer.
Step by step
Solved in 4 steps with 1 images
