Гра "П'яниця"#10248

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

1 секунда

256 мегабайтів

Легка

У Віталія та Богдана є $2 n$ карт. Кожна карта має значення від $1$ до $2 n$ . Кожне значення зустрічається у рівно одної карти.

Віталію дано $n$ карт з того набору, Богдану — усі інші.

Вони грають у гру "П'яниця", тобто тасують свої карти, а потім беруть зі своєї колоди верхню карту. У кого значення карти більше — той отримує бал. Вони грають $n$ раундів, тобто поки не закінчаться карти.

Визначіть мінімальну та максимальну кількість балів, які може отримати Віталій.

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5 ) — кількість карт у кожного з гравців.

Другий рядок містить $n$ цілих різних чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n ( $1 \leq a_{i} \leq 2 n$ 1 \le a_i \le 2n) — значення карт Віталія.

Вихідні дані

Виведіть два цілі числа — мінімальну та максимальну кількість балів, які може отримати Віталій.

Приклади

Приклад 1

Приклад 2

Примітка

У першому прикладі у Віталія карти $1, 4, 5$ , у Богдана — $2, 3, 6$ . Один з можливих сценаріїв:

Віталій кладе $1$ , Богдан - $6$ . Богдан отримує бал, бо $1 < 6$ 1<6.
Віталій кладе $4$ , Богдан - $2$ . Віталій отримує бал, бо $4 > 2$ 4>2.
Віталій кладе $5$ , Богдан - $3$ . Віталій отримує бал, бо $5 > 3$ 5>3.

Віталій отримав два бали.

Інший сценарій:

Віталій кладе $1$ , Богдан - $2$ . Богдан отримує бал, бо $1 < 2$ 1<2.
Віталій кладе $4$ , Богдан - $6$ . Богдан отримує бал, бо $4 < 6$ 4<6.
Віталій кладе $5$ , Богдан - $3$ . Віталій отримує бал, бо $5 > 3$ 5>3.

Віталій отримав один бал.

Якщо перебрати всі варіанти, то можна впевнитися, в тому що Віталій не може отримати менше одного або більш як два бали.

У другому прикладі у Віталія карти $4, 5, 6$ , у Богдана — $1, 2, 3$ . Будь-яка карта Віталія більша за будь-яку карту Богдана, отже Віталій завжди набирає рівно $3$ бали.

Оцінювання

Рішення, які працюють правильно для обмежень $1 \leq n \leq 2000$ 1 \le n \le 2\,000, набиратимуть $40%$ балів.