Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_22_08 - Detektyw Monk

Kiedy Adrian Monk wszedł do mieszkania świadka, od razu rzuciły mu się w oczy albumy ze zdjęciami, ponumerowane liczbami od 1 do n. Zbiory fotografii nie są ustawione na półce w porządku rosnącym, co bardzo drażni naszego bohatera. Adrian postanowił je poukładać. W każdym ruchu Monk weźmie jeden lub więcej bezpośrednio sąsiadujących ze sobą albumów i przełoży je w inne miejsce na półce. Nasz bohater może wykonać dowolną liczbę ruchów. Zakładamy, że na półce znajdują się wyłącznie tomy z fotografiami.

Odpowiedz na pytanie w ilu minimalnie ruchach Adrian Monk może uporządkować dany zbiór albumów?

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita t ∈ [1;10] określająca liczbę zestawów danych. W kolejnych liniach znajdują się zestawy danych.

Pierwsza linia każdego zestawu danych zawiera jedną liczbę całkowitą n ∈ [2;9] oznaczającą ilość albumów ze zdjęciami. W kolejnej linii znajduje się permutacja liczb od 1 do n określająca kolejność w jakiej tomy fotografii są ustawione na półce.

Wyjście

Na wyjściu należy wypisać minimalną liczbę ruchów jakie powinien wykonać nasz bohater, aby ustawić albumy w kolejności rosnącej.

Przykład

Wejście

1
6
6 5 4 3 2 1

Wyjście

4

Wyjaśnienie do przykładu

Monk może poukładać albumy wykonując następujące ruchy (przesuwane tomy zostały pogrubione):

  • 6 5 4 3 2 1
  • 5 6 4 3 2 1
  • 3 2 5 6 4 1
  • 3 4 1 2 5 6
  • 1 2 3 4 5 6

Dodane przez:Maciej Boniecki
Data dodania:2015-04-25
Limit czasu wykonania programu:0.300s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.