У Віталія та Богдана є 2n карт. Кожна карта має значення від 1 до 2n. Кожне значення зустрічається у рівно одної карти.
Віталію дано n карт з того набору, Богдану — усі інші.
Вони грають у гру "П'яниця", тобто тасують свої карти, а потім беруть зі своєї колоди верхню карту. У кого значення карти більше — той отримує бал. Вони грають n раундів, тобто поки не закінчаться карти.
Визначіть мінімальну та максимальну кількість балів, які може отримати Віталій.
Перший рядок містить одне ціле число n (1≤n≤105) — кількість карт у кожного з гравців.
Другий рядок містить n цілих різних чисел a1,a2,…,an (1≤ai≤2n) — значення карт Віталія.
Виведіть два цілі числа — мінімальну та максимальну кількість балів, які може отримати Віталій.
У першому прикладі у Віталія карти 1,4,5, у Богдана — 2,3,6. Один з можливих сценаріїв:
Віталій кладе 1, Богдан - 6. Богдан отримує бал, бо 1<6.
Віталій кладе 4, Богдан - 2. Віталій отримує бал, бо 4>2.
Віталій кладе 5, Богдан - 3. Віталій отримує бал, бо 5>3.
Віталій отримав два бали.
Інший сценарій:
Віталій кладе 1, Богдан - 2. Богдан отримує бал, бо 1<2.
Віталій кладе 4, Богдан - 6. Богдан отримує бал, бо 4<6.
Віталій кладе 5, Богдан - 3. Віталій отримує бал, бо 5>3.
Віталій отримав один бал.
Якщо перебрати всі варіанти, то можна впевнитися, в тому що Віталій не може отримати менше одного або більш як два бали.
У другому прикладі у Віталія карти 4,5,6, у Богдана — 1,2,3. Будь-яка карта Віталія більша за будь-яку карту Богдана, отже Віталій завжди набирає рівно 3 бали.
Рішення, які працюють правильно для обмежень 1≤n≤2000, набиратимуть 40% балів.