Zigzags (Codeforces 1400D)
Tags: Math, combinatorics

You are given an array $$$a_1, a_2 \dots a_n$$$. Calculate the number of tuples $$$(i, j, k, l)$$$ such that:   $$$1 \le i < j < k < l \le n$$$;  $$$a_i = a_k$$$ and $$$a_j = a_l$$$; 

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$4 \le n \le 3000$$$) — the size of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the array $$$a$$$.It's guaranteed that the sum of $$$n$$$ in one test doesn't exceed $$$3000$$$.

Output: For each test case, print the number of described tuples.

Note: In the first test case, for any four indices $$$i < j < k < l$$$ are valid, so the answer is the number of tuples.In the second test case, there are $$$2$$$ valid tuples:   $$$(1, 2, 4, 6)$$$: $$$a_1 = a_4$$$ and $$$a_2 = a_6$$$;  $$$(1, 3, 4, 6)$$$: $$$a_1 = a_4$$$ and $$$a_3 = a_6$$$. 

Sample Inputs:
2
5
2 2 2 2 2
6
1 3 3 1 2 3

Sample Outputs:
5
2

Solution (Python):
from itertools import accumulate as acm, compress as cp
for __ in range(int(input())):
    n = int(input())
    arr = tuple(map(int, input().split()))
    ans = 0
    count = [0] * 3001
    for i in range(n):
        ans += sum(cp(acm(map(count.__getitem__, arr[i + 1:])), map(lambda x: arr[i] == x, arr[i + 2:])))
        count[arr[i]] += 1
    print(ans)

Solution (Python):
from sys import stdin

def inp():
    return stdin.buffer.readline().rstrip().decode('utf8')

def itg():
    return int(stdin.buffer.readline())

def mpint():
    return map(int, stdin.buffer.readline().split())
from itertools import accumulate as acm, compress as cp
for __ in range(itg()):
    n = itg()
    arr = tuple(mpint())
    ans = 0
    count = [0] * 3001
    for i in range(n):
        ans += sum(cp(acm(map(count.__getitem__, arr[i + 1:])), map(lambda x: arr[i] == x, arr[i + 2:])))
        count[arr[i]] += 1
    print(ans)

Solution (Python):
from itertools import accumulate as acm, compress as cp
for __ in range(int(input())):
    n = int(input())
    arr = tuple(map(int, input().split()))
    ans = 0
    count = [0] * 3001
    for i in range(n):
        ans += sum(cp(acm(map(count.__getitem__, arr[i + 1:])), map(lambda x: arr[i] == x, arr[i + 2:])))
        count[arr[i]] += 1
    print(ans)