Domácí kolo

B: Skleníky

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Soutež skončila. Získané body již nejdou do výsledků.

Zadání (Řešení)

Během prvních průzkumů planety Ma-stra výzkumníci narazili na nový, zvláštní druh rostliny, vyskytující se na planetě v širokém rozmezí velikostí. Celkem se zatím podařilo najít N exemplářů, každý jinak vysoký.

Tuto rostlinu ale můžeme v laboratořích pěstovat pouze ve zvláštním skleníku, který umí simulovat neobvyklé venkovní podnebí Ma-stry. Všechny rostliny jsme do něj umístili do řady. Protože se ale jedná o zkušební verzi skleníku, má své zvláštnosti – jediné, co můžeme dělat, je (i několikrát) vzít rostlinu z levého konce skleníku a přenést ji na pravý konec, a naopak přenést rostlinu z pravého konce na levý. Skleník je přitom dostatečně velký z obou stran na to, abychom mohli přesuny z jednoho konce na druhý opakovat, kolikrát se nám zachce. Abychom rostliny mohli přenášet, máme k dispozici pouze jednu přenosnou komoru, do níž můžeme na chvíli jednu rostlinu umístit. Navíc nemůžeme žádnou rostlinu odložit mimo tuto komoru, protože by okamžitě zvadla.

Abychom lépe pochopili zvláštnosti flory Ma-stry, chceme si rostliny uvnitř skleníku seřadit podle velikosti, ať na nich poté můžeme provádět experimenty. Je to za těchto podmínek možné? A pokud ano, kolik nejméně rostlin budeme muset přesunout?

Tvar vstupu

Ve vstupním souboru je na prvním řádku číslo T udávající počet zadání v souboru. Každé zadání pak vypadá následovně:

Na prvním řádku je přirozené číslo N udávající počet rostlin ve skleníku. Na dalším řádku je posloupnost N různých přirozených čísel, kde i-té číslo udává výšku i-té rostliny. Máte zaručeno, že v posloupnosti neexistuje dvojice stejných čísel.

Tvar výstupu

Do výstupního souboru vypište pro každý vstup na samostatný řádek jedno číslo – nejmenší počet přesunů potřebných k seřazení rostlin. Za správné považujeme vzestupné i sestupné seřazení. Pokud rostliny seřadit nelze, vypište -1.

Lehká verze

  • T ≤ 15 – počet testovacích vstupů
  • 1 ≤ N ≤ 1 000 – počet rostlin
  • 1 ≤ výška rostliny ≤ 10 000

Těžká verze

  • T ≤ 10 – počet testovacích vstupů
  • 1 ≤ N ≤ 1 000 000 – počet rostlin
  • 1 ≤ výška rostliny ≤ 5 000 000

Ukázkový vstup

3
5
3 4 7 8 11
7
21 20 17 5 3 30 28
7
2 4 6 8 3 5 7

Ukázkový výstup

0
2
-1

Vysvětlení ukázkového vstupu a výstupu

V prvním vstupu jsou rostliny ve správném pořadí, není proto potřeba žádný přesun.

Ve vstupu druhém lze postupně přesunout rostliny o výšce 28 a 30 na druhý konec skleníku, čímž budou všechny rostliny seřazeny. Správná odpověď je tedy 2.

V posledním vstupu není možné realizovat takovou sérii přesunů, po které by byly rostliny seřazeny. Pro takový případ je správnou odpovědí číslo -1.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)