RoboContest

Xotira 32 MB Vaqt 1000 ms

14

Tartiblash #3

Robot fabrikada nomerlangan qutilarni tartibga solish bilan shug‘ullanadi. U oldidagi stol ustida N ta uzunligi turlicha bo‘lgan qutilarni ko‘radi. Ushbu qutilar chapdan o‘ngga qarab quyidagi tartibda joylashgan: : $a_1,a_2,a_3,...,a_N$

Robot qutilarni faqat o‘sish tartibida joylashtirishi kerak, ya’ni chapdan o‘ngga qarab bloklarning uzunliklari oshib borishi kerak.

Biroq, u faqat quyidagi operatsiyani bajara oladi:

U har qanday $i$ -chi qutini faqat $i + K$ - chi quti bilan almashtira oladi.
Agar $i + K$ indeksli quti mavjud bo‘lmasa, bunday almashtirish mumkin emas.

Robot qutilarni tartiblash uchun minimal qancha almashtirish talab etishini hisoblash dasturi tuzilsin

Kiruvchi ma'lumotlar:

Birinchi qatorda N va K sonlar beriladi. $(1 ≤ K≤N ≤ 1000)$

Ikkinchi qatorda N ta $a₁, a₂, ..., aₙ$ sonlar beriladi. $(1 ≤ aᵢ ≤ 10⁹)$

Chiquvchi ma'lumotlar:

Tartiblashga ketadigan minimal amal soni chop eting. Agar tartibga solish imkonsiz bo‘lsa, -1 ni chop eting.

Misollar

#	input.txt	output.txt
1	6 2 8 6 5 3 1 10	4
2	4 3 5 7 2 11	-1

Izoh:

1-testda.
8 6 5 3 1 10
↓
5 6 8 3 1 10
↓
5 3 8 6 1 10
↓
5 3 1 6 8 10
↓
1 3 5 6 8 10

RoboContest

Masala #YHATIOZEDZ

Tartiblash #3