Doprogramovanie do: 24. august 2020 23:59
10 dní
Popisy už neodovzdávajte. Ešte stále však môžete odosielať vaše programy, za ktoré dostanete časť bodov.
Počet bodov:
Popis:  12b
Program:  8b

Predseda Kúl Spolku Pandemiológov sa v rámci aktuálnej krízy rozhodol zvolať zasadnutie odborníkov zo všetkých krajov. Takéto zasadnutie je veľmi prestížne a prirodzene tak má určité absurdné pravidlá. Jedno z nich je napríklad to, že sa zasadá vždy výlučne za okrúhlim stolom a každý kraj má pri danom stole svoje pevne stanovené miesto. Preto každý, kto si sadne na miesto daného kraju, musí rozprávať iba o tom konkrétnom kraji. Každý odborník, ktorý sedí na mieste svojho kraju je tak výrazne efektívnejší ako keď sedí na mieste iného kraju o ktorom nič nevie.

Odborníci sú tvrdohlavé stvorenia a za stôl si sadajú v poradí, v ktorom prišli do miestnosti a odmietajú si presadnúť. Predseda avšak potrebuje presné informácie z čo najviac krajov a tie mu vie dať iba odborník z daného kraja. Jedinou možnosťou ako tento stav dosiahnuť, je otočiť stôl o niekoľko miest do ktorejkoľvek strany tak, aby čo najviac odborníkov sedelo na svojom mieste. A keďže stôl je veľmi ťažký, ideálne ho chce otočiť o čo najmenej miest.

Úloha

Tvojou úlohou je pomôcť predsedovi určiť o koľko najmenej miest treba otočiť okrúhly stôl tak, aby čo najviac odborníkov sedelo na svojom mieste. Predsedu taktiež zaujíma koľko odborníkov tak bude sedieť na svojom mieste. Odborníci si sadajú za stôl v poradí v akom prišli, odborník \(n_i\) si tak vždy sadne na pozíciu \(i\). Odborník sedí na svojom mieste vtedy, ak je z kraja \(i\) a zároveň sedi na mieste \(i\) pri stole. Stôl je možné otočiť do oboch strán.

Formát vstupu

Na prvom riadku vstupu dostanete číslo \(n\), (\(1 \leq n \leq 10^6\)), ktoré označuje počet krajov z ktorých prichádzajú jednotlivý odborníci. Na druhom riadku sa nachádza \(n\) čísiel \(n_i\), (\(1 \leq n_i \leq n\)) označujúcich kraj z ktorého pochádza \(i\)-ty oborník. Každé čislo od \(1\) po \(n\) sa na vstupe nachádza práve raz.

Formát výstupu

Na výstup vypíš dve čísla, \(k\) - posun stola, \(t\) - počet odborníkov na svojom mieste, tak aby čo najviac odborníkov sedelo na svojom mieste.

Príklady

Input:

5
3 4 5 2 1

Output:

2 3

Ak otočíme stôl o dve miesta, odborníci 3, 4 a 5 budú sedieť na svojom mieste.

Input:

4
4 1 2 3

Output:

1 4

Prvý prišiel odborník zo štvrtého kraja, následne už prišli odborníci po poradí. Stôl nám tak stačí otočiť o jedno miesto aby všetci odborníci sedeli na mieste so správnym číslom.

Input:

4
2 3 4 1

Output:

1 4

Podobne ako pri predchádzajpcom príklade nám stačí otočiť stôl iba o jedno miesto, tento krát avšak do druhej strany.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.