Read problem statements in [Mandarin], [Vietnamese], and [Russian] as well.

For a given array B_{1}, B_{2}, \ldots, B_{M} of length at least 3, let's define its weight as the largest value of (B_{i}-B_{j})\cdot(B_{j}-B_{k}) over all possible triples (i, j, k) with 1 ≤ i, j, k ≤ M and i \neq j, j \neq k, k \neq i. 

You are given a sorted array A_{1}, A_{2}, \ldots, A_{N} (that is, A_{1} ≤ A_{2} ≤ \ldots ≤ A_{N}). 

Calculate the sum of weights of all contiguous subarrays of A of length at least 3. That is, count the sum of weights of arrays [A_{i}, A_{i+1}, \ldots, A_{j}] over all 1 ≤ i < j ≤ N with j-i≥ 2.

------ 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 second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N}.

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

For each test case, print a single line containing the sum of weights of all subarrays of A of length at least 3.

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

$1 ≤T ≤1000$
$3 ≤N ≤3000$
$1 ≤A_{1} ≤A_{2} \ldots ≤A_{N} ≤10^{6}$.
- Sum of $N$ over all test cases won't exceed $6000$.

----- Sample Input 1 ------ 
2
4
1 2 3 4
5
1 42 69 228 2021 
----- Sample Output 1 ------ 
4
1041808

----- explanation 1 ------ 
Explanation of the first test case of the sample: 

Given array has $3$ subarrays of length at least $3$.

$[1, 2, 3]$ has weight $1$, with $i = 1, j = 2, k = 3$: $(1-2)\cdot(2-3) = 1$ 
$[2, 3, 4]$ has weight $1$, with $i = 3, j = 2, k = 1$: $(4-3)\cdot(3-2) = 1$ 
$[1, 2, 3, 4]$ has weight $2$, with $i = 1, j = 2, k = 4$: $(1-2)\cdot(2-4) = 2$, or with $i = 1, j = 3, k = 4$: $(1-3)\cdot(3-4) = 2$

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting

Complete search

Mathematics

Matrices

Data structures


Solutions:
def compute(A):
	ans = 0
	N = len(A)
	for i in range(N):
		k = i + 1
		for j in range(i + 2, N):
			mid = (A[i] + A[j]) / 2
			while k < j - 1 and abs(A[k + 1] - mid) <= abs(A[k] - mid):
				k += 1
			ans += (A[k] - A[i]) * (A[j] - A[k])
	return ans
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	print(compute(A))


import sys

def compute(A):
	ans = 0
	N = len(A)
	for i in range(N):
		k = i + 1
		for j in range(i + 2, N):
			mid = (A[i] + A[j]) / 2
			while k < j - 1 and abs(A[k + 1] - mid) <= abs(A[k] - mid):
				k += 1
			ans += (A[k] - A[i]) * (A[j] - A[k])
	return ans
T = int(sys.stdin.readline())
for i in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().strip().split()))
	print(compute(A))


def compute(arr):
	n = len(arr)
	total = 0
	for i in range(n - 2):
		j = i + 1
		for k in range(i + 2, n):
			mid = (arr[i] + arr[k]) / 2
			while j < k - 1 and abs(arr[j + 1] - mid) <= abs(arr[j] - mid):
				j += 1
			total += (arr[i] - arr[j]) * (arr[j] - arr[k])
	return total
for t in range(int(input())):
	n = int(input())
	print(compute(list(map(int, input().split()))))


def op(arr, n):
	tot = 0
	for i in range(n - 2):
		j = i + 1
		for k in range(i + 2, n):
			mid = (arr[i] + arr[k]) // 2
			while j < k - 1 and abs(arr[j + 1] - mid) <= abs(arr[j] - mid):
				j += 1
			tot += (arr[i] - arr[j]) * (arr[j] - arr[k])
	return tot
for _ in range(int(input())):
	n = int(input())
	li = [int(x) for x in input().split()]
	print(op(li, n))


import sys

def compute(arr):
	n = len(arr)
	total = 0
	for i in range(n - 2):
		j = i + 1
		for k in range(i + 2, n):
			mid = (arr[i] + arr[k]) / 2
			while j < k - 1 and abs(arr[j + 1] - mid) <= abs(arr[j] - mid):
				j += 1
			total += (arr[i] - arr[j]) * (arr[j] - arr[k])
	return total
t = int(sys.stdin.readline())
for t_itr in range(t):
	n = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().strip().split()))
	sys.stdout.write(str(compute(arr)) + '\n')


from sys import stdin

def uniq_cnt(arr):
	uniq = []
	cnt = []
	c = arr[0] - 1
	for a in arr:
		if a == c:
			cnt[-1] += 1
		else:
			uniq.append(a)
			cnt.append(1)
			c = a
	return (uniq, cnt)

def sum_of_weights(arr):
	(uniq, cnt) = uniq_cnt(arr)
	n = len(uniq)
	if n < 3:
		return 0
	swt = 0
	for lx in range(n - 2):
		L = uniq[lx]
		C = cnt[lx]
		M = uniq[lx + 1]
		mx = lx + 2
		Mn = uniq[mx]
		for hx in range(lx + 2, n):
			H = uniq[hx]
			while mx < hx:
				if M - L >= H - Mn:
					break
				M = Mn
				mx += 1
				Mn = uniq[mx]
			swt += (H - M) * (M - L) * C * cnt[hx]
	return swt
inp = stdin.readline
T = int(inp())
for tx in range(T):
	N = int(inp())
	Ays = list(map(int, inp().split()))
	print(sum_of_weights(Ays))


from sys import stdin

def sum_of_weights(arr, n):
	swt = 0
	for lx in range(n - 2):
		L = arr[lx]
		M = arr[lx + 1]
		mx = lx + 2
		Mn = arr[mx]
		for hx in range(lx + 2, n):
			H = arr[hx]
			while mx < hx:
				if M - L > H - Mn:
					break
				M = Mn
				mx += 1
				Mn = arr[mx]
			swt += (H - M) * (M - L)
	return swt
inp = stdin.readline
T = int(inp())
for tx in range(T):
	N = int(inp())
	Ays = list(map(int, inp().split()))
	print(sum_of_weights(Ays, N))


import sys

def compute(a):
	ans = 0
	for i in range(n):
		j = i + 1
		for k in range(i + 2, n):
			x = (a[i] + a[k]) / 2
			while j < k - 1 and abs(a[j + 1] - x) <= abs(a[j] - x):
				j = j + 1
			ans += (a[j] - a[i]) * (a[k] - a[j])
	return ans
t = int(sys.stdin.readline())
for t_itr in range(t):
	n = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().strip().split()))
	sys.stdout.write(str(compute(arr)) + '\n')


import bisect

def func(N, A):
	i = 0
	s = 0
	ans = 0
	for i in range(N - 2):
		k = i + 1
		for j in range(i + 2, N):
			mid = (A[j] + A[i]) // 2
			while k < j - 1 and abs(A[k + 1] - mid) <= abs(A[k] - mid):
				k += 1
			ans += (A[k] - A[i]) * (A[j] - A[k])
	return ans
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	print(func(N, A))


def main():
	for t in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		total = 0
		for i in range(n - 2):
			j = i + 1
			for k in range(i + 2, n):
				avg = (arr[i] + arr[k]) / 2
				while j < k - 1 and abs(arr[j + 1] - avg) <= abs(arr[j] - avg):
					j += 1
				total += (arr[j] - arr[i]) * (arr[k] - arr[j])
		print(total)
main()


import sys

def calculate(lks):
	n = len(lks)
	ans = 0
	for i in range(n - 2):
		j = i + 1
		for k in range(i + 2, n):
			mid = (lks[i] + lks[k]) / 2
			while j < k - 1 and abs(lks[j + 1] - mid) <= abs(lks[j] - mid):
				j += 1
			ans += (lks[k] - lks[j]) * (lks[j] - lks[i])
	return ans
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	lks = list(map(int, sys.stdin.readline().strip().split()))
	sys.stdout.write(str(calculate(lks)) + '\n')