Masala #1178

Xotira 16 MB Vaqt 1000 ms

Massiv tengligi

Sizga N ta sondan tashkil topgan A massivi berilgan. Siz massiv ustida quyidagi amalni cheksiz marotaba bajarishingiz mumkin.

A massiv orasidan K ta ketma-ket kelgan sonlarni tanlang va ularni hammasini shu ketma-ketlikning minimum soniga tenglang.

Topshiriq esa massivni minimal amallar orqali hamma elementlarini bir-biriga tenglashdir.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida T (1 ≤ T < \(10^5\))

Har bir T uchun birinchi qatorida N va K butun sonlari (1 ≤ K≤ N ≤ \(10^5\)) N - massiv elementlari soni va K - ketma-ketlik uzunligi. T ta N ning umumiy yig'indisi ≤\(10^6\)..

Har bir T uchun ikkinchi qatorida N ta sondan tashkil topgan A massivi, \(a_1, a_2,...,a_N\), (1 ≤ \(a_i\) ≤ \(10^5\)) - massiv elementlari.

Chiquvchi ma'lumotlar:

Agar tenglashni iloji bo'lsa minimal amallar sonini, agarda iloji bo'lmasa -1 chop eting.

Misollar

#	input.txt	output.txt
1	3 11 4 1 16 20 7 1 9 3 16 17 16 13 11 5 17 15 11 1 8 20 14 9 18 11 4 8 2 15 2 11 16 6 18 3 16	3 3 7
2	1 5 2 2 4 10 15 1	4
3	4 10 3 16 10 2 15 5 7 7 16 10 11 4 3 20 4 18 1 9 5 12 5 14 16 14 16 10 4 4 6 3 13 19 4 8 3 16	5 2 2 3

input.txt

output.txt

3
11 4
1 16 20 7 1 9 3 16 17 16 13 
11 5
17 15 11 1 8 20 14 9 18 11 4 
8 2
15 2 11 16 6 18 3 16

3
3
7

1
5 2
2 4 10 15 1

4
10 3
16 10 2 15 5 7 7 16 10 11 
4 3
20 4 18 1 
9 5
12 5 14 16 14 16 10 4 4 
6 3
13 19 4 8 3 16