Two independent sensors each emit a sorted (non-decreasing) stream of integer readings. Their combined length is guaranteed to be odd, so the merged multiset has a single middle element. Print that median value: the element that would sit in the middle if both streams were merged into one sorted list.
Either stream may be empty (but not both, since the total is at least one). Solve it without materializing a full merge in the worst case — a logarithmic-style search on the values or partitions is expected.
Input format
Line 1: an integer n, the length of the first stream.
Line 2: n space-separated integers in non-decreasing order (this line is empty if n is 0).
Line 3: an integer m, the length of the second stream.
Line 4: m space-separated integers in non-decreasing order (this line is empty if m is 0).
Output format
A single integer: the median of the merged readings.
Constraints
- 0 <= n, m and 1 <= n + m <= 200000
- n + m is odd.
- -1000000000 <= each reading <= 1000000000
- Each stream is sorted in non-decreasing order.