Median-D&C

from typing import List, Tuple
import math



def get_mid_members_of_even_length_array(arr: List[int], l: int, h: int) -> Tuple[int, int]:
    return arr[(l + h) // 2], arr[(l + h) // 2 + 1]


def get_median_of_sorted_array(arr: List[int], l: int, h: int) -> float:
    size = h - l + 1

    if size % 2 == 0:
        return sum(get_mid_members_of_even_length_array(arr, l, h)) / 2
    else:
        return float(arr[(l + h) // 2])


def find_median_of_sorted_arrays(arr1: List[int], arr2: List[int], l1: int, h1: int, l2: int, h2: int) -> float:
    size = h1 - l1 + 1

    if size == 0:
        return 0

    if size == 1:
        return (arr1[l1] + arr2[l2]) / 2

    if size == 2:
        return (max(arr1[l1], arr2[l2]) + min(arr1[h1], arr2[h2])) / 2


    if size % 2 == 0:
        mid_arr1_1, mid_arr1_2 = get_mid_members_of_even_length_array(arr1, l1, h1)
        mid_arr2_1, mid_arr2_2 = get_mid_members_of_even_length_array(arr2, l2, h2)


        if mid_arr1_1 >= mid_arr2_1 and mid_arr1_2 <= mid_arr2_2:
            return get_median_of_sorted_array(arr1, l1, h1)

        if mid_arr1_1 <= mid_arr2_1 and mid_arr1_2 >= mid_arr2_2:
            return get_median_of_sorted_array(arr2, l2, h2)

    med_arr1 = get_median_of_sorted_array(arr1, l1, h1)
    med_arr2 = get_median_of_sorted_array(arr2, l2, h2)

    if med_arr1 == med_arr2:
        return med_arr1

    if med_arr1 < med_arr2:
        return find_median_of_sorted_arrays(arr1, arr2, math.ceil((l1 + h1) / 2), h1, l2, (l2 + h2) // 2)
    return find_median_of_sorted_arrays(arr1, arr2, l1, (l1 + h1) // 2, math.ceil((l2 + h2) / 2), h2)



def main():
    n = int(input())
    arr1 = list(map(int, input().split()))
    arr2 = list(map(int, input().split()))
    ans = find_median_of_sorted_arrays(arr1, arr2, 0, n - 1, 0, n - 1)
    print(ans)

if __name__ == "__main__":
    main()