e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Olympiad in Informatics, II Stage, II Round

E. Гра "П'яниця"

У Віталія та Богдана є $2n$ карт. Кожна карта має значення від $1$ до $2n$. Кожне значення зустрічається у рівно одної карти. Віталію дано $n$ карт з того набору, Богдану~--- усі інші. Вони грають у гру "П'яниця", тобто тасують свої карти, а потім беруть зі своєї колоди верхню карту. У кого значення карти більше~--- той отримує бал. Вони грають $n$ раундів, тобто поки не закінчаться карти. Визначіть мінімальну та максимальну кількість балів, які може отримати Віталій. \InputFile Перший рядок містить одне ціле число $n$ ($1 \le n \le 10^5 $) --- кількість карт у кожного з гравців. Другий рядок містить $n$ цілих різних чисел $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2n$) --- значення карт Віталія. \OutputFile Виведіть два цілі числа~--- мінімальну та максимальну кількість балів, які може отримати Віталій. \Note У першому прикладі у Віталія карти $1,4,5$, у Богдана~--- $2,3,6$. Один з можливих сценаріїв: \begin{enumerate} \item Віталій кладе $1$, Богдан - $6$. Богдан отримує бал, бо $1<6$. \item Віталій кладе $4$, Богдан - $2$. Віталій отримує бал, бо $4>2$. \item Віталій кладе $5$, Богдан - $3$. Віталій отримує бал, бо $5>3$. \end{enumerate} Віталій отримав два бали. Інший сценарій: \begin{enumerate} \item Віталій кладе $1$, Богдан - $2$. Богдан отримує бал, бо $1<2$. \item Віталій кладе $4$, Богдан - $6$. Богдан отримує бал, бо $4<6$. \item Віталій кладе $5$, Богдан - $3$. Віталій отримує бал, бо $5>3$. \end{enumerate} Віталій отримав один бал. Якщо перебрати всі варіанти, то можна впевнитися, в тому що Віталій не може отримати менше одного або більш як два бали. У другому прикладі у Віталія карти $4,5,6$, у Богдана~--- $1,2,3$. Будь-яка карта Віталія більша за будь-яку карту Богдана, отже Віталій завжди набирає рівно $3$ бали. \Scoring Рішення, які працюють правильно для обмежень $1 \le n \le 2\,000$, набиратимуть $40\%$ балів.
Time limit 1 second
Memory limit 256 MiB
Input example #1
3
1 4 5
Output example #1
1 2
Input example #2
3
5 4 6
Output example #2
3 3
Author Mykhailo Perekopskyi
Source Ukrainian Olympiad in Informatics 2021, II Stage