Gigel a cumpărat de la magazinul de dulciuri N caramele din cele T tipuri disponibile. Când a ajuns acasă le-a aşezat pe raft în linie. Din motive estetice, Gigel vrea să rearanjeze caramelele astfel încât cele de acelaşi tip să formeze o secvenţă continuă pe raft.
Pentru a rearanja caramelele Gigel va folosi un singur tip de mutare: se iau două caramele aflate pe poziţii consecutive în rand şi se interschimbă.
Cerinţă
Ajutaţi-l pe Gigel să-şi aranjeze caramelele cumpărate folosind un număr minim de mutări.
Date de intrare
Fişierul de intrare caramele.in conţine pe prima linie numerele naturale N şi T separate prin spaţiu. Pe cea de a doua linie este descris şirul caramelelor, aşa cum sunt aşezate iniţial pe raft. Caramelele sunt identificate după tip cu un număr întreg cuprins între 1 şi T.
Date de ieşire
Fişierul de ieşire caramele.out va conţine o singură linie pe care se va scrie un singur număr întreg reprezentând numărul minim de mutări necesare pentru a aranja caramelele.
Restricţii
1 ≤ T ≤ 10
1 ≤ N ≤ 10 000
Pentru 60% din teste T ≤ 7 şi N ≤ 1 000
Exemple
caramele.in
caramele.out
Explicaţii
8 3
1 1 2 1 2 3 2 3
2
Se interschimbă caramelele de pe poziţiile 3 şi 4 şi cele de pe poziţiile 6 şi 7.
5 3
3 2 1 3 2
3
Se interschimbă caramelele de pe poziţiile 3 şi 4, apoi cele de pe poziţiile 2 şi 3 şi în final cele de pe poziţiile 3 şi 4