paintball

După amiază la Iezăreni cei $N$ membri ai lotului naţional de informatică vor participa la o partidă mai specială de paintball. Fiecare concurent va primi o armă şi o singură bilă cu vopsea.
În primul rând concurenţii sunt numerotaţi de la $1$ la $N$. Având o singură bilă, fiecare concurent se gândeşte dinainte în cine va trage. Un concurent care a fost împuşcat cu o bilă de vopsea este declarat “mort” şi nu mai poate să tragă.
Concurenţii trag succesiv, în orice ordine doresc.

Cerinţă

Să se determine numărul minim şi numărul maxim de “morţi”.

Date de intrare

Fişierul de intrare paintball.in conţine pe prima linie numărul natural $N$ reprezentând numărul de concurenţi. Pe cea de a două linie sunt scrise $N$ numere naturale separate prin spaţii; al $i$-lea număr de pe linie reprezentând numărul concurentului în care va trage concurentul $i$.

Date de ieșire

Fişierul de ieşire paintball.out va conţine o singură linie pe care vor fi scrise două numere naturale separate prin spaţiu $nr_{min} \ nr_{max}$ reprezentând numărul minim şi respectiv numărul maxim de “morţi”.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$;
• Un concurent se poate împuşca pe sine însuşi.

Exemplu

paintball.in

8
2 3 2 2 6 7 8 5

paintball.out

3 5

Explicație

Dacă de exemplu ordinea în care trag concurenţii este $1, 4, 3, 5, 7$ vor muri $2, 6, 8$ (număr minim de morţi).
Dacă ordinea este: $2, 1, 4, 7, 6, 5$ vor muri $3, 2, 8, 7, 6$ (număr maxim de morţi).