Description

During the XXXX-th NOI, to strengthen exchanges among provincial contestants, the organizers decided to hold an inter-provincial e-sports tournament. Each province’s team consists of $n$ players. The event is the popular online game Paopaotang. Before each match, both coaches submit a lineup that fixes the playing order; once submitted, it cannot be changed. In the match, the No. 1 players, No. 2 players, ..., No. $n$ players face off pairwise, for a total of $n$ games. A win yields $2$ points, a draw $1$ point, and a loss $0$ points. The total score is the sum of the single-game points; the team with the higher total advances (if the totals are equal, the winner is decided by drawing lots).

As the leader of Team Zhejiang, you have already learned the skill levels of all players from every province and measure each by a strength value. To simplify the problem, we assume players are not affected by any external factors: a stronger player always defeats a weaker player, and two players with equal strength always draw. Since the opponent’s strategy for choosing the order is completely unknown, all teams adopt the strategy of deciding the playing order completely at random.

Of course, you do not want to compete without clarity. You want to know in advance, in the best and worst cases, how many points Team Zhejiang can obtain.

Input Format

The first line contains an integer $n$, the number of players on each team.

The next $n$ lines each contain one integer, the strength values of the $n$ players on Team Zhejiang.

The following $n$ lines each contain one integer, the strength values of the opponent’s $n$ players.

Output Format

Output two integers separated by a space, representing the best and the worst possible total points that Team Zhejiang can obtain. Do not output extra spaces at the end of the line.

2
1
3
2
4

2 0

6
10000000
10000000
10000000
10000000
10000000
10000000
0
0
0
0
0
0

12 12

Hint

Sample explanation

1: We name the $4$ players $A, B, C, D$. The following $4$ types of matchups may occur. In the best case, Zhejiang can get $2$ points; in the worst case, it gets $0$ points.

2: The opponents are all diligent students who do not play games. No matter how they arrange the order, they cannot change the outcome. Team Zhejiang always achieves a clean sweep.

Constraints

• For $20\%$ of the testdata, $1 \leq n \leq 10$.
• For $40\%$ of the testdata, $1 \leq n \leq 100$.
• For $60\%$ of the testdata, $1 \leq n \leq 1000$.
• For $100\%$ of the testdata, $1 \leq n \leq 100000$, and all players’ strength values are between $0$ and $10000000$.

Translated by ChatGPT 5