Median of Two Sorted Arrays

You are given two sorted arrays. Your task is to merge them and find the median of the combined sorted array.

The median is defined as follows:

• If the total number of elements, \( n \), is odd, the median is the element at index \( \frac{n+1}{2} \) (using 1-indexing).
• If \( n \) is even, the median is given by \( \frac{a+b}{2} \), where \( a \) and \( b \) are the two middle elements.

Note: The arrays may be of different lengths. At least one of the arrays is non-empty.

Input is read from standard input (stdin) and output should be written to standard output (stdout).

inputFormat

The input consists of four lines:

1. The first line contains an integer \( n_1 \), the number of elements in the first array.
2. The second line contains \( n_1 \) space-separated integers representing the first sorted array.
3. The third line contains an integer \( n_2 \), the number of elements in the second array.
4. The fourth line contains \( n_2 \) space-separated integers representing the second sorted array.

If an array is empty, its corresponding size will be 0 and the next line will be blank.

outputFormat

Output a single line containing the median of the two sorted arrays. If the median is a non-integer, output it as a float.

## sample

2
1 2
2
3 4

2.5