Bubble Battle: Best‐Case and Worst‐Case Scoring

In the XXXX-th NOI, to boost communication among contestants from different provinces, the organizers held an inter‐provincial e‐sports competition. Each province’s team consists of n players and they play the classic online game Bubble Hall. Before a match, both coaches submit a list determining the order in which their players will play. In the match, the first player from one team competes with the first player of the other team, the second with the second, and so on, for a total of n rounds. The scoring is as follows:

• Win: 2 points
• Draw (if the two players have equal strength): 1 point
• Loss: 0 points

Every player’s ability is measured by a strength value. In every round, if player a (with strength \(a\)) competes against player b (with strength \(b\)), then

[ f(a,b)=\begin{cases} 2, & \text{if } a>b,\ 1, & \text{if } a=b,\ 0, & \text{if } a<b. \end{cases} ]

While every team chooses their playing order uniformly at random, as the team leader of the Zhejiang team you know the strength values of all players (both in your team and the opposing province). Being proactive, you wish to know, if you could select your order, what is the best possible total score and the worst guaranteed total score your team can end up with when facing an arbitrary ordering of the opponents.

More formally, you are given two arrays of n integers each. The first array represents the strengths of the Zhejiang team players, and the second represents the strengths of the opposing team. By choosing an ordering for your team, the opponent’s team order (a permutation of their players) may affect the outcome. The best-case score is the maximum total score that can be achieved by some pairing (i.e. some bijection between the two teams) and the worst-case score is the minimum total score that can be forced by an adversarial ordering of the opponent after you fix your order.

Input Format: The input begins with an integer n. The next line contains n integers denoting the strengths of the Zhejiang team, and the third line contains n integers denoting the strengths of the opposing team.

Note: When comparing two players with strengths \(a\) and \(b\), the game outcome is decided solely by their relative values.

Output Format: Output two integers separated by a space: the maximum total score (best-case) and the minimum total score (worst-case) that the Zhejiang team can obtain.

Explanation of the Strategy:

It turns out that the maximum total score can be achieved by an optimal pairing strategy. One way to compute it is via a greedy algorithm inspired by the classical "Tian Ji Horse Racing" problem. Specifically, if we sort both arrays in ascending order and then use the following strategy:

• Maintain two pointers for each array (low and high).
• If the smallest remaining player in Zhejiang has a strength greater than the smallest remaining opponent, pair them (a win: 2 points) and move both pointers forward.
• Otherwise, if Zhejiang’s strongest remaining player is greater than the opponent’s strongest remaining player, pair them (win) and move the corresponding pointers backward.
• If neither yields a win, then sacrifice the weakest Zhejiang player by pairing it with the opponent’s strongest player. In case of equality during sacrifice, a draw (1 point) is earned.

The worst-case score is obtained by assuming that after you fix your (optimal) ordering the opponent arranges their players in ascending order. In that case, simply pairing the sorted lists element‐by‐element will yield the worst-case outcome: for each pair, Zhejiang gets 2 points if its player is stronger, 1 point if equal, and 0 otherwise.

Your task is to compute both scores.

inputFormat

The first line contains an integer n (\(1 \le n \le 10^5\)).

The second line contains \(n\) integers: \(a_1, a_2, \dots, a_n\) representing the strengths of the Zhejiang team.

The third line contains \(n\) integers: \(b_1, b_2, \dots, b_n\) representing the strengths of the opposing team.

outputFormat

Output two integers separated by a space: the best-case total score and the worst-case total score.

sample

2
3 5
3 4

3 3