def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m
 
    # create temp arrays
    L = [0] * (n1)
    R = [0] * (n2)
 
    # Copy data to temp arrays L[] and R[]
    for i in range(0, n1):
        L[i] = arr[l + i]
 
    for j in range(0, n2):
        R[j] = arr[m + 1 + j]
 
    # Merge the temp arrays back into arr[l..r]
    i = 0     # Initial index of first subarray
    j = 0     # Initial index of second subarray
    k = l     # Initial index of merged subarray
 
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
 
    # Copy the remaining elements of L[], if there
    # are any
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
 
    # Copy the remaining elements of R[], if there
    # are any
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1
    
    return arr
# l is for left index and r is right index of the
# sub-array of arr to be sorted
 
 
def mergeSort(arr, l, r):
    if l < r-1:
 
        # Same as (l+r)//2, but avoids overflow for
        # large l and h
        m = l+(r-l)//2
        print(l, m, r)
        # Sort first and second halves
        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)


# def merge(arr: list, left: int, mid: int, right: int):



#     # length = right-left
#     # arr = [None] * (length)
#     # print(result)

#     # array_left = arr[left:mid]
#     # array_right = arr[mid:right]
#     # print(array_left, array_right)

#     n1 = mid - left + 1
#     n2 = right - mid
 
#     # create temp arrays
#     array_left = [0] * (n1)
#     array_right = [0] * (n2)
 
#     # Copy data to temp arrays L[] and R[]
#     for i in range(0, n1):
#         array_left[i] = arr[left + i]
 
#     for j in range(0, n2):
#         array_right[j] = arr[mid + 1 + j]

#     l = 0
#     r = 0
    
#     k = left


#     while (l < len(array_left) and r < len(array_right)):
#         if array_left[l] <= array_right[r]:
#             arr[k] = array_left[l]
#             l += 1
#         else:
#             arr[k] = array_right[r]
#             r += 1
#         k += 1
    
#     # print(arr, k, l, r)
    
#     while l < len(array_left):
#         arr[k] = array_left[l]
#         l += 1
#         k += 1

#     while r < len(array_right):
#         arr[k] = array_right[r]
#         r += 1
#         k += 1

#     return arr



def merge_sort(arr: list, left: int, right: int):

    if left < right:
        mid = left + (right-left) // 2

        print(left, mid, right)
        print(arr)

        merge_sort(arr, left, mid)
        merge_sort(arr, mid+1, right)
        merge(arr, left, mid, right)


def test():
    # a = [1, 4, 9, 2, 10, 11]
    # b = merge(a, 0, 3, 6)
    # print(b)
    # expected = [1, 2, 4, 9, 10, 11]
    # assert b == expected
    c = [1, 4, 2, 10, 1, 2]
    mergeSort(c, 0 , len(c)-1)
    print(c)
    expected = [1, 1, 2, 2, 4, 10]
    print(expected)
    # assert c == expected


test()
def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m
 
    # create temp arrays
    L = [0] * (n1)
    R = [0] * (n2)
 
    # Copy data to temp arrays L[] and R[]
    for i in range(0, n1):
        L[i] = arr[l + i]
 
    for j in range(0, n2):
        R[j] = arr[m + 1 + j]
 
    # Merge the temp arrays back into arr[l..r]
    i = 0     # Initial index of first subarray
    j = 0     # Initial index of second subarray
    k = l     # Initial index of merged subarray
 
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
 
    # Copy the remaining elements of L[], if there
    # are any
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
 
    # Copy the remaining elements of R[], if there
    # are any
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1
    
    return arr
# l is for left index and r is right index of the
# sub-array of arr to be sorted
 
 
def mergeSort(arr, l, r):
    if l < r-1:
 
        # Same as (l+r)//2, but avoids overflow for
        # large l and h
        m = l+(r-l)//2
        print(l, m, r)
        # Sort first and second halves
        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)


# def merge(arr: list, left: int, mid: int, right: int):



#     # length = right-left
#     # arr = [None] * (length)
#     # print(result)

#     # array_left = arr[left:mid]
#     # array_right = arr[mid:right]
#     # print(array_left, array_right)

#     n1 = mid - left + 1
#     n2 = right - mid
 
#     # create temp arrays
#     array_left = [0] * (n1)
#     array_right = [0] * (n2)
 
#     # Copy data to temp arrays L[] and R[]
#     for i in range(0, n1):
#         array_left[i] = arr[left + i]
 
#     for j in range(0, n2):
#         array_right[j] = arr[mid + 1 + j]

#     l = 0
#     r = 0
    
#     k = left


#     while (l < len(array_left) and r < len(array_right)):
#         if array_left[l] <= array_right[r]:
#             arr[k] = array_left[l]
#             l += 1
#         else:
#             arr[k] = array_right[r]
#             r += 1
#         k += 1
    
#     # print(arr, k, l, r)
    
#     while l < len(array_left):
#         arr[k] = array_left[l]
#         l += 1
#         k += 1

#     while r < len(array_right):
#         arr[k] = array_right[r]
#         r += 1
#         k += 1

#     return arr



def merge_sort(arr: list, left: int, right: int):

    if left < right:
        mid = left + (right-left) // 2

        print(left, mid, right)
        print(arr)

        merge_sort(arr, left, mid)
        merge_sort(arr, mid+1, right)
        merge(arr, left, mid, right)


def test():
    # a = [1, 4, 9, 2, 10, 11]
    # b = merge(a, 0, 3, 6)
    # print(b)
    # expected = [1, 2, 4, 9, 10, 11]
    # assert b == expected
    c = [1, 4, 2, 10, 1, 2]
    mergeSort(c, 0 , len(c)-1)
    print(c)
    expected = [1, 1, 2, 2, 4, 10]
    print(expected)
    # assert c == expected


test()
# create temp arrays # Copy data to temp arrays L[] and R[] # Merge the temp arrays back into arr[l..r] # Initial index of first subarray # Initial index of second subarray # Initial index of merged subarray # Copy the remaining elements of L[], if there # are any # Copy the remaining elements of R[], if there # are any # l is for left index and r is right index of the # sub-array of arr to be sorted # Same as (l+r)//2, but avoids overflow for # large l and h # Sort first and second halves # def merge(arr: list, left: int, mid: int, right: int): #     # length = right-left #     # arr = [None] * (length) #     # print(result) #     # array_left = arr[left:mid] #     # array_right = arr[mid:right] #     # print(array_left, array_right) #     n1 = mid - left + 1 #     n2 = right - mid #     # create temp arrays #     array_left = [0] * (n1) #     array_right = [0] * (n2) #     # Copy data to temp arrays L[] and R[] #     for i in range(0, n1): #         array_left[i] = arr[left + i] #     for j in range(0, n2): #         array_right[j] = arr[mid + 1 + j] #     l = 0 #     r = 0 #     k = left #     while (l < len(array_left) and r < len(array_right)): #         if array_left[l] <= array_right[r]: #             arr[k] = array_left[l] #             l += 1 #         else: #             arr[k] = array_right[r] #             r += 1 #         k += 1 #     # print(arr, k, l, r) #     while l < len(array_left): #         arr[k] = array_left[l] #         l += 1 #         k += 1 #     while r < len(array_right): #         arr[k] = array_right[r] #         r += 1 #         k += 1 #     return arr # a = [1, 4, 9, 2, 10, 11] # b = merge(a, 0, 3, 6) # print(b) # expected = [1, 2, 4, 9, 10, 11] # assert b == expected # assert c == expected