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 nrmin nrmax reprezentând numărul minim şi respectiv numărul maxim de “morţi”.
Restricţii
1 ≤ N ≤ 1 000 000
Un concurent se poate împuşca pe sine însuşi.
Exemple
paintball.in
paintball.out
Explicaţii
8
2 3 2 2 6 7 8 5
3 5
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).