Duel of Cards

Interview

Time limit1sMemory limit2048 MB

Summary

Given Alice's n cards out of 2n, find the minimum and maximum number of rounds she can win over all possible deck orders.

Level: Medium4 of 10
Topics: Greedy, Sorting, Two pointers
Solved: No attempts yet

Problem

Alice and Bob play a card game with $2n$ cards numbered uniquely from $1$ to $2n$ . The cards are shuffled and dealt so that each player gets $n$ cards. Each player arranges their cards into a deck in any order they choose, face down.

The game has $n$ turns. In each turn, both players reveal the top card of their deck and compare the two numbers. The player with the larger card scores one point. This repeats until all cards in both decks have been compared.

After receiving her $n$ cards, Alice wants to know the minimum and maximum number of points she may score in the game.

Input

The first line contains a single integer $n$ ( $1 \le n \le 1\,000$ ), the number of cards Alice gets.

Each of the next $n$ lines contains one integer between $1$ and $2n$ (inclusive), a card dealt to Alice. All the cards are distinct.

Output

Print two integers: the minimum and the maximum number of points Alice may score.

Examples1

Example 1
Input
```
3
2
5
4
```
Expected output
```
1 2
```