You are given an array A = [A_{1}, A_{2}, \ldots, A_{N}] containing N integers.

Consider any subarray [A_{L}, A_{L+1}, \ldots, A_{R}] of this subarray (where 1≤ L ≤ R ≤ N). Ther weirdness of this subarray, denoted w(L, R), is defined to be the number of indices L ≤ i ≤ R such that A_{i} equals the number of occurrences of A_{i} in this subarray.

Formally, we define w(L, R) for 1 ≤ L ≤ R ≤ N as follows:
For every integer x, let f_{L, R}(x) denote the number of indices L ≤ j ≤ R such that A_{j} = x.
w(L, R) then equals the number of L ≤ i ≤ R such that A_{i} = f_{L, R}(A_{i})

For example, let A = [1, 3, 5, 2, 1, 2, 9, 5]. Then,
w(1, 8) = 2, which can be computed as follows.
We have
- f_{1, 8}(1) = 2
- f_{1, 8}(2) = 2
- f_{1, 8}(3) = 1
- f_{1, 8}(5) = 2
- f_{1, 8}(9) = 1

The only indices which satisfy f_{1, 8}(A_{i}) = A_{i} are i = 4 and i = 6, and hence w(1, 8) = 2.
w(3, 5) = 1 — the subarray is [5, 2, 1], and each of 1, 2, 5 occur exactly once in this subarray. Of these, only 1 equals the number of its occurrences in this subarray.

Given A, your task is to compute the sum of the weirdness of all subarrays of A, i.e, the value
\sum_{L = 1}^{N} \sum_{R = L}^N w(L, R)

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N, the size of the given array.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} — the elements of A.

------ Output Format ------ 

For each test case, output a single line containing a single integer — the sum of the weirdness of all subarrays of the given array.

------ Constraints ------ 

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{6}$
$1 ≤ A_{i} ≤ 10^{6}$
- The sum of $N$ across all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
4
3
3 3 3
4
1 2 1 2
5
1 2 3 2 1
8
1 2 2 3 2 3 3 1
----- Sample Output 1 ------ 
3
10
16
54

----- explanation 1 ------ 
Test Case 1: The only subarray with non-zero weirdness is the whole array, which has $w(1, 3) = 3$ because every value is $3$ and it appears thrice.

Test Case 2: There are $10$ subarrays. Their weirdness values are as follows:
- $w(1, 1) = 1$, because $A_{1} = 1$ and $f_{1, 1}(1) = 1$.
- $w(1, 2) = 1$, because $A_{1} = 1$ and $f_{1, 2}(1) = 1$; but $A_{2} = 2$ and $f_{1, 2}(2) = 1 \neq 2$.
- $w(1, 3) = 0$, here $f_{1, 3}(1) = 2 \neq 1$ and $f_{1, 3}(2) = 1 \neq 2$ so no index satisfies the condition.
- $w(1, 4) = 2$, here indices $2$ and $4$ satisfy the condition.
- $w(2, 2) = 0$
- $w(2, 3) = 1$, index $3$ satisfies the condition.
- $w(2, 4) = 3$, all indices satisfy the condition.
- $w(3, 3) = 1$
- $w(3, 4) = 1$, index $3$ satisfies the condition.
- $w(4, 4) = 0$

Difficulty: VERY_HARD
Tags: Data structures

Amortized analysis

Mathematics

Greedy algorithms
Skill types: Amortized analysis

Data structures

Greedy algorithms

Starter code:

Solutions:
def correction(lst, n, m):
	lst.append(n)
	lst.append(None)
	for i in range(m, -1, -1):
		lst[i + 1] = lst[i]
	lst[0] = -1

def solve():
	n = int(input())
	arr = [[] for i in range(n + 1)]
	count = 0
	for x in map(int, input().split()):
		if x <= n:
			arr[x].append(count)
		count += 1
	ans = 0
	for j in range(n + 1):
		l1 = arr[j]
		m = len(l1)
		if m >= j:
			correction(l1, n, m)
			k = 1
			while k + j - 1 < m + 1:
				(L, R) = (k, k + j - 1)
				ans += (l1[L] - l1[L - 1]) * (l1[R + 1] - l1[R]) * j
				k += 1
	print(ans)
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	for i in range(n):
		x[i] = [x[i], i]
	x = sorted(x)
	xd = []
	xd += [x[0][0], [x[0][1]]]
	for i in range(1, n):
		if x[i][0] == x[i - 1][0]:
			xd[-1] += [x[i][1]]
		else:
			xd += [x[i][0], [x[i][1]]]
	xd = {xd[i]: xd[i + 1] for i in range(0, len(xd), 2)}
	ans = 0
	for (k, v) in xd.items():
		if len(v) > k:
			temp = 0
			temp += (v[0] + 1) * (v[k] - v[k - 1])
			for i in range(1, len(v)):
				if i + k < len(v):
					temp += (v[i] - v[i - 1]) * (v[i + k] - v[i + k - 1])
				elif i + k == len(v):
					temp += (v[i] - v[i - 1]) * (n - v[i + k - 1])
				else:
					break
			ans += temp * k
		elif len(v) == k:
			ans += k * (v[0] + 1) * (n - v[k - 1])
	print(ans)


import sys
input = sys.stdin.readline

def solve(a, x):
	m = len(a)
	if m == 0:
		return 0
	ans = 0
	for i in range(m - x + 1):
		(L, R) = (i, i + x - 1)
		l = a[L] - (a[L - 1] if L else -1)
		r = (a[R + 1] if R + 1 < m else n) - a[R]
		ans += l * r
	return ans
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	b = [[] for _ in range(n + 1)]
	for (i, x) in enumerate(lst):
		if x <= n:
			b[x].append(i)
	print(sum((solve(v, i) * i for (i, v) in enumerate(b))))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	hm = {}
	for i in range(len(arr)):
		if arr[i] in hm:
			hm[arr[i]].append(i)
		else:
			hm[arr[i]] = [i]
	ans = 0
	for i in hm:
		x = len(hm[i])
		if x >= i:
			l = 0
			r = i - 1
			temp = 0
			while r < x:
				if l == 0:
					left = hm[i][l] + 1
				else:
					left = hm[i][l] - hm[i][l - 1]
				if r == x - 1:
					right = n - hm[i][r]
				else:
					right = hm[i][r + 1] - hm[i][r]
				temp += left * right
				l += 1
				r += 1
			ans += temp * i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	adict = {}
	for i in range(n):
		if a[i] in adict:
			adict[a[i]].append(i)
		else:
			adict[a[i]] = [i]
	w = 0
	for key in adict:
		alist = adict[key]
		prev = 0
		for i in range(len(alist) - (key - 1)):
			last = alist[i + key - 1]
			if i == len(alist) - (key - 1) - 1:
				next = n
			else:
				next = alist[i + key - 1 + 1]
			front = alist[i] + 1 - prev
			back = next - last
			w += front * back * key
			prev = alist[i] + 1
	print(w)


def read_int_ist():
	lst = list(map(int, input().split(' ')))
	return lst

def read_int_values():
	return map(int, input().split(' '))

def solve(len1, a) -> int:
	ans = 0
	lst_indices = [[] for _ in range(len1 + 1)]
	for i in range(1, len(a) + 1):
		if a[i - 1] <= len1:
			lst_indices[a[i - 1]].append(i)
	for x in range(1, n + 1):
		lst_index = list(lst_indices[x])
		lst_index.insert(0, 0)
		lst_index.insert(len(lst_index), n + 1)
		for i in range(1, len(lst_index) - x):
			ans += x * (lst_index[i] - lst_index[i - 1]) * (lst_index[i + x] - lst_index[i + x - 1])
	return ans
for _ in range(int(input())):
	n = int(input())
	lst = read_int_ist()
	print(solve(n, lst))


from typing import DefaultDict
from math import sqrt
from collections import OrderedDict, defaultdict
import math

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def ncr_modulo(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def dict_ele_count(l):
	d = DefaultDict(lambda : 0)
	for ele in l:
		d[ele] += 1
	return d

def max_in_dict(d):
	maxi = 0
	for ele in d:
		if d[ele] > maxi:
			maxi = d[ele]
	return maxi

def element_count(s):
	l = []
	k = s[0]
	c = 0
	for ele in s:
		if ele == k:
			c += 1
		else:
			l.append([k, c])
			k = ele
			c = 1
	l.append([k, c])
	return l
for _ in range(int(input())):
	bool = True
	flag = True
	n = int(input())
	l = list(map(int, input().split()))
	mod = 10 ** 9 + 7
	ans = 0
	d = defaultdict(lambda : [])
	for i in range(n):
		d[l[i]].append(i)
	for ele in d:
		if len(d[ele]) >= ele:
			for i in range(len(d[ele]) - ele + 1):
				if i == 0:
					x = d[ele][i] + 1
				else:
					x = d[ele][i] - d[ele][i - 1]
				if i == len(d[ele]) - ele:
					y = n - d[ele][i + ele - 1]
				else:
					y = d[ele][i + ele] - d[ele][i + ele - 1]
				ans += x * y * ele
	print(ans)


import math
t = int(input())
for _ in range(t):
	number = int(input())
	list_number = list(map(int, input().split()))
	map_number = {}
	for i in range(number):
		current_number = list_number[i]
		if current_number in map_number:
			map_number[current_number].append(i + 1)
		else:
			map_number[current_number] = []
			map_number[current_number].append(i + 1)
	for i in map_number:
		map_number[i].insert(0, 0)
		map_number[i].append(number + 1)
	ans = 0
	for i in map_number:
		current = map_number[i]
		length = len(map_number[i])
		for j in range(1, length - i):
			ans += i * ((current[j] - current[j - 1]) * (current[j + i] - current[j + i - 1]))
	print(ans)


for tc in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	freq = dict()
	for x in ls:
		if freq.get(x) is None:
			freq[x] = 1
		else:
			freq[x] += 1
	dis = dict()
	for x in range(len(ls)):
		if freq[ls[x]] >= ls[x]:
			if dis.get(ls[x]) is None:
				dis[ls[x]] = [x]
			else:
				dis[ls[x]].append(x)
	res = 0
	for x in dis:
		ta = 0
		prev = 0
		for r in range(x - 1, len(dis[x])):
			leftSena = dis[x][ta] - prev + 1
			if r == len(dis[x]) - 1:
				rightSena = len(ls) - 1 - dis[x][r] + 1
			else:
				rightSena = dis[x][r + 1] - 1 - dis[x][r] + 1
			res += leftSena * rightSena * x
			prev = dis[x][ta] + 1
			ta += 1
	print(res)


for t in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	dic = {}
	count = 0
	for i in range(N):
		if A[i] not in dic:
			dic[A[i]] = []
		dic[A[i]].append(i)
	for i in dic.keys():
		if len(dic.get(i)) < i:
			continue
		temp = []
		temp += dic.get(i)
		temp.insert(0, -1)
		temp.append(N)
		for j in range(1, len(temp) - i):
			count += i * (temp[j] - temp[j - 1]) * (temp[i + j] - temp[i + j - 1])
	print(count)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if l[i] not in d:
			d[l[i]] = [0, i + 1]
		else:
			d[l[i]].append(i + 1)
	ans = 0
	for (k, v) in d.items():
		v.append(n + 1)
		if len(v) >= k + 2:
			l = 1
			r = l + k - 1
			temp = 0
			while r < len(v) - 1:
				temp += abs(v[l] - v[l - 1]) * abs(v[r] - v[r + 1])
				l += 1
				r += 1
			ans += temp * k
	print(ans)


from collections import *
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	d = defaultdict(list)
	for j in range(n):
		d[l[j]].append(j)
	for j in d:
		li = 0
		ui = n - 1
		dl = d[j]
		q = len(dl)
		r = q - j
		if r < 0:
			continue
		else:
			for k in range(r + 1):
				u = dl[k + j - 1]
				l = dl[k]
				if k == 0:
					li = 0
				else:
					li = dl[k - 1] + 1
				if k + j >= q:
					ui = n - 1
				else:
					ui = dl[k + j] - 1
				ans += (ui - u + 1) * (l - li + 1) * j
	print(ans)


import sys
from collections import deque

def f(l, n, f):
	a = 0
	x = n - 1
	while a <= x:
		m = a + (x - a) // 2
		if l[m] == f:
			return m
		elif l[m] > f:
			x = m - 1
		else:
			a = m + 1
	return None
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	l = list(map(int, sys.stdin.readline().split()))
	d = {}
	for i in range(n):
		if l[i] in d:
			d[l[i]].append(i)
		else:
			d.update({l[i]: deque([i])})
	ans = 0
	for x in d:
		if len(d[x]) < x:
			continue
		else:
			d[x].append(n)
			d[x].appendleft(-1)
			s = 0
			for i in range(1, len(d[x]) - x):
				y = (d[x][i + x] - d[x][i + x - 1]) * (d[x][i] - d[x][i - 1])
				s = s + y
			ans = ans + x * s
	print(ans)


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	sys.stderr = open('error.txt', 'w')
depth = 200001
mod = 1000000007
lim = mod * mod
sys.setrecursionlimit(depth)
linp = lambda : list(minp())
minp = lambda : map(int, input().split())
from math import inf, ceil, sqrt, log2, gcd
from collections import defaultdict, deque
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def expo(a, b):
	if not b:
		return 1
	v = expo(a, b // 2)
	v = v * v % mod
	if b % 2:
		v = v * a % mod
	return v

def modinv(a, b):
	d = expo(b, mod - 2)
	v = a * d % mod
	return v

def checkPrime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	for i in range(3, int(sqrt(n)) + 1, 2):
		if n % i == 0:
			return False
	return True

def highestPowerof2(x):
	x |= x >> 1
	x |= x >> 2
	x |= x >> 4
	x |= x >> 8
	x |= x >> 16
	return x ^ x >> 1
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a) + 1
	dp = defaultdict(lambda : [0])
	for i in range(n):
		dp[a[i]].append(i + 1)
	a = list(set(a))
	for i in a:
		dp[i].append(n + 1)
	ans = 0
	for i in a:
		if len(dp[i]) - 2 < i:
			continue
		res = 0
		for j in range(i, len(dp[i]) - 1):
			l = dp[i][j - i + 1] - dp[i][j - i]
			r = dp[i][j + 1] - dp[i][j]
			res = res + l * r
		res = res * i
		ans = ans + res
	print(ans)


from collections import *
for u in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = defaultdict(list)
	for i in range(n):
		d[l[i]].append(i)
	s = 0
	for i in d:
		(a, b) = (1, 1)
		m = len(d[i])
		for j in range(m):
			if j - 1 >= 0:
				a = d[i][j] - d[i][j - 1]
			else:
				a = d[i][j] + 1
			if j + i - 1 < m:
				if j + i < m:
					b = d[i][j + i] - d[i][j + i - 1]
				else:
					b = n - 1 - d[i][j + i - 1] + 1
				s += a * b * i
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	freq = []
	d = {}
	for i in range(len(a)):
		if a[i] in d:
			d[a[i]] += [i]
		else:
			d[a[i]] = [-1, i]
	result = 0
	for item in d:
		if len(d[item]) < item:
			continue
		d[item] += [n]
		l = 1
		r = item
		while r < len(d[item]) - 1:
			ans = (d[item][l] - d[item][l - 1]) * (d[item][r + 1] - d[item][r]) * item
			result += ans
			r += 1
			l += 1
	print(result)