Median of Two Sorted Arrays

You are given two sorted arrays. Your task is to find the median of the two arrays combined. The median is defined as the middle element when the arrays are merged into one sorted array. If the total number of elements is even, the median is given by \(\frac{a+b}{2}\), where \(a\) and \(b\) are the two middle elements.

The input is provided via stdin and the result should be printed to stdout.

inputFormat

The input consists of four lines:

1. An integer \(n\) representing the number of elements in the first array.
2. \(n\) space-separated integers representing the first sorted array. If \(n=0\), this line will be empty.
3. An integer \(m\) representing the number of elements in the second array.
4. \(m\) space-separated integers representing the second sorted array. If \(m=0\), this line will be empty.

outputFormat

Output a single line containing the median of the two sorted arrays as a floating point number.

2
1 3
1
2

2.0