Read problems statements [Mandarin] , [Bengali] , [Hindi] , [Russian] and [Vietnamese] as well.

Chef's brother Chefu is a competitive programmer. Every day, he practices for ICPC (International Chefs' Programming Contest) by solving problems. Today, Chef challenged his brother to solve a certain problem, promising to bake an apple pie for him if he succeeds. Chefu has successfully solved the problem, but can you solve it? 

You are given an integer sequence $A_{1}, A_{2}, \ldots, A_{N}$. In one move, you must select two adjacent elements of this sequence (i.e. $A_{i}$ and $A_{i+1}$ for some valid $i$) and swap them. Let's call a sequence *orderly* if it contains a contiguous subsequence with length at least $K$ such that all of its elements have identical values. Find the minimum number of moves required to make the given sequence orderly or determine that it is impossible.

------  Input ------
The first line of the 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 two space-separated integers $N$ and $K$. 
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer — the minimum required number of moves, or $-1$ if it is impossible to make the sequence orderly.

------  Constraints  ------
$1 ≤ T ≤ 1,000$
$2 ≤ K ≤ N ≤ 300,000$
$1 ≤ A_{i} ≤ 300,000$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (30 points):
$N ≤ 100$
the sum of $N$ over all test cases does not exceed $1,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
2
8 3
1 2 2 1 3 3 2 1
5 3
1 1 2 2 3
----- Sample Output 1 ------ 
3
-1

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Data structures

Range queries

Greedy algorithms


Solutions:
from collections import Counter
from collections import defaultdict
for z in range(int(input())):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	a = list(map(int, input().split()))
	c = Counter(a)
	d = defaultdict(list)
	fl = []
	f = 0
	for (x, y) in c.items():
		if y >= k:
			f = 1
			fl.append(x)
	if not f:
		print('-1')
	else:
		for i in range(n):
			d[a[i]].append(i)
		mdif = pow(10, 10)
		for i in fl:
			dif = 0
			if k % 2:
				for j in range(k):
					dif += abs(d[i][j] - d[i][k // 2]) - abs(j - k // 2)
				q = 0
				for j in range(k // 2 + 1, len(d[i]) - k // 2):
					q += d[i][j + k // 2] - d[i][j] - (d[i][j - 1] - d[i][j - 1 - k // 2])
					if q < 0:
						dif += q
						q = 0
			else:
				for j in range(k):
					dif += abs(d[i][j] - d[i][k // 2]) - abs(j - k // 2)
				q = 0
				for j in range(k // 2 + 1, len(d[i]) - k // 2 + 1):
					q += d[i][j + k // 2 - 1] - d[i][j] - (d[i][j - 1] - d[i][j - 1 - k // 2]) + d[i][j] - d[i][j - 1]
					if q < 0:
						dif += q
						q = 0
			mdif = min(dif, mdif)
		print(mdif)


t = int(input())
for _ in range(t):
	(n, k) = [int(k) for k in input().split()]
	A = [int(k) for k in input().split()]
	g = []
	for _ in range(300000):
		g.append([])
	for i in range(n):
		g[A[i] - 1].append(i)
	flag = True
	m = 10 ** 15
	for f in g:
		if len(f) >= k:
			flag = False
			s = 0
			for i in range(k):
				s += abs(f[i] - f[k // 2])
			m = min(m, s)
			if k % 2 == 0:
				for i in range(len(f) - k):
					s += abs(f[i + k] - f[i + k // 2])
					s -= abs(f[i] - f[i + k // 2])
					m = min(m, s)
			else:
				for i in range(len(f) - k):
					s += 1 * abs(f[i + k // 2] - f[i + k // 2 + 1])
					s += abs(f[i + k] - f[i + k // 2 + 1])
					s -= abs(f[i] - f[i + k // 2 + 1])
					m = min(m, s)
	if flag:
		print(-1)
	else:
		if k % 2 == 0:
			m = m - k / 4 * (k / 2 + 1) - k / 4 * (k / 2 - 1)
		else:
			m = m - k // 2 * (k // 2 + 1)
		print(int(m))