Annettuna on lista, jossa on n kokonaislukua. Jokainen luku väliltä 1 \dots n esiintyy listalla tarkalleen kerran.

Keräät luvut listalta järjestyksessä 1,2,\dots,n yhden tai useamman kierroksen avulla. Joka kierroksella käyt listan läpi vasemmalta oikealle ja keräät mahdollisimman paljon seuraavaksi järjestyksessä tulevia lukuja.

Ennen ensimmäistä kierrosta sinun tulee kuitenkin vaihtaa keskenään kaksi eri listan lukua. Mikä on pienin määrä kierroksia, jos toimit optimaalisesti, ja monellako tavalla voit tehdä tällaisen vaihdon?

Huomaa, että sinun tulee vaihtaa keskenään kaksi lukua tasan kerran alussa ennen ensimmäistä kierrosta. Sinun tulee vaihtaa luvut, vaikka tämä lisäisi kierrosten määrää verrattuna lähtötilanteeseen.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: listan pituus.

Seuraavalla rivillä on n lukua: listan sisältö.

Tuloste

Tulosta kaksi kokonaislukua: pienin kierrosten määrä ja mahdollisten vaihtojen määrä.

Esimerkki

Syöte:

8
6 1 4 5 7 3 8 2

Tuloste:

3 5

Selitys: Jos toimit optimaalisesti, voit kerätä luvut 3 kierroksella. Mahdolliset vaihdot ovat (1,3), (2,3), (2,4), (2,5) ja (3,6).

Osatehtävä 1 (13 pistettä)

• 2 \le n \le 100

Osatehtävä 2 (23 pistettä)

• 2 \le n \le 5000

Osatehtävä 3 (64 pistettä)

• 2 \le n \le 2 \cdot 10^5