Guaranteed Matching Gloves

Professor Acid Rain, known for his "acid rain", has a dark basement with two drawers of gloves. One drawer holds left-hand gloves and the other holds right-hand gloves. Each drawer contains gloves in \(n\) different colors, and for each color the number of gloves in the left and right drawers may differ. However, it is guaranteed that there is at least one color available in both drawers so that a matching pair can be found.

The professor wants to perform an experiment that can only be successful if he carries a matching pair (i.e. one left-hand and one right-hand glove of the same color) to the laboratory. Since the basement is completely dark, he cannot tell the color of a glove until he is back in the lab. Moreover, he hates to go down to the basement more than once and also dislikes carrying extra gloves if not needed. Therefore, he wishes to determine the minimum number of gloves to extract from each drawer such that, regardless of which gloves are picked (in the worst-case scenario), there is guaranteed to be at least one matching pair.

This problem can be solved using the pigeonhole principle. In the worst case, if the professor picks \(L\) gloves from the left drawer and \(R\) gloves from the right drawer and if all picked gloves are of distinct colors (note that in each drawer, at most \(n\) distinct colors can be obtained), then to avoid the possibility of having no matching color across drawers, the total number of gloves picked must exceed \(n\). In other words, we must have:

[ L + R > n ]

The minimum total number that satisfies this condition is \(n+1\). One optimal strategy is to pick \(\lfloor \frac{n+1}{2} \rfloor\) gloves from the left drawer and \(n+1 - \lfloor \frac{n+1}{2} \rfloor\) gloves from the right drawer.

Your task is to implement this strategy. Note that the counts of gloves for each color in each drawer are provided via input, but they do not affect the calculation since each drawer inherently has gloves in all \(n\) colors. You only need to make sure that the number of gloves picked from each drawer, when summed up, equals \(n+1\).

inputFormat

The input is given in three lines:

• The first line contains a single integer \(n\) representing the number of colors.
• The second line contains \(n\) positive integers representing the number of gloves available for each color in the left glove drawer.
• The third line contains \(n\) positive integers representing the number of gloves available for each color in the right glove drawer.

outputFormat

Output two integers separated by a space. The first integer is the number of gloves to take from the left drawer, and the second integer is the number of gloves to take from the right drawer.

sample

3
1 1 1
1 1 1

2 2