

from __future__ import annotations





def  _snake_case		(snake_case_					:     List[str]    ,       snake_case_					:     List[Any]  )							->		List[Any]:
  __UpperCAmelCase	:  Any		=     0
  __UpperCAmelCase	:  Any		=     len(__A  ) - 1
  while left <= right:
    __UpperCAmelCase	:  str		=     (left + right) // 2
    if left == right:
      if sorted_list[middle] < item:
        __UpperCAmelCase	:  Dict		=     middle + 1
      break
    elif sorted_list[middle] < item:
      __UpperCAmelCase	:  Any		=     middle + 1
    else:
      __UpperCAmelCase	:  Tuple		=     middle - 1
  sorted_list.insert(__A    ,       __A  )
  return sorted_list





def  _snake_case		(snake_case_					:     List[Any]    ,       snake_case_					:     Any  )							->		Optional[Any]:
  __UpperCAmelCase	:  int		=     []
  while left and right:
    if left[0][0] < right[0][0]:
      result.append(left.pop(0  )  )
    else:
      result.append(right.pop(0  )  )
  return result + left + right





def  _snake_case		(snake_case_					:     int  )							->		Tuple:
  __UpperCAmelCase	:  Dict		=     len(__A  )
  if length <= 1:
    return list_ad
  __UpperCAmelCase	:  Optional[int]		=     length // 2
  return merge(sortlist_ad(list_ad[:middle]  )    ,       sortlist_ad(list_ad[middle:]  )  )





def  _snake_case		(snake_case_					:     Optional[int]  )							->		List[Any]:

  if len(__A  ) <= 1:
    return collection
  __UpperCAmelCase	:  str		=     []
  __UpperCAmelCase	:  int		=     False
  for i in range(0    ,       len(__A  )    ,       2  ):
    if i == len(__A  ) - 1:
      __UpperCAmelCase	:  Optional[int]		=     True
    else:
      if collection[i] < collection[i + 1]:
        two_paired_list.append([collection[i], collection[i + 1]]  )
      else:
        two_paired_list.append([collection[i + 1], collection[i]]  )
  __UpperCAmelCase	:  Optional[Any]		=     sortlist_ad(__A  )
  __UpperCAmelCase	:  int		=     [i[0] for i in sorted_list_ad]
  result.append(sorted_list_ad[-1][1]  )
  if has_last_odd_item:
    __UpperCAmelCase	:  Optional[int]		=     collection[-1]
    __UpperCAmelCase	:  int		=     binary_search_insertion(__A    ,       __A  )
  __UpperCAmelCase	:  Tuple		=     False
  for i in range(len(__A  ) - 1  ):
    if result[i] == collection[-1] and has_last_odd_item:
      __UpperCAmelCase	:  Optional[int]		=     True
    __UpperCAmelCase	:  Tuple		=     sorted_list_ad[i][1]
    # If last_odd_item is inserted before the item's index,
    # you should forward index one more.
    if is_last_odd_item_inserted_before_this_index:
      __UpperCAmelCase	:  str		=     result[: i + 2] + binary_search_insertion(result[i + 2 :]    ,       __A  )
    else:
      __UpperCAmelCase	:  Union[str, Any]		=     result[: i + 1] + binary_search_insertion(result[i + 1 :]    ,       __A  )

  return result


if __name__ == "__main__":
      _SCREAMING_SNAKE_CASE							 =			input('''Enter numbers separated by a comma:\n''').strip()
      _SCREAMING_SNAKE_CASE							 =			[int(item) for item in user_input.split(''',''')]
      print(merge_insertion_sort(unsorted))








from typing import SupportsIndex

import numpy as np
from scipy.ndimage import convolve





def 				__a							(       __A			,							__A			,							__A						):
    SCREAMING_SNAKE_CASE__         =    np.stack((horizontal_flow, vertical_flow)			,							2						)

    # Create a grid of all pixel coordinates and subtract the flow to get the
    # target pixels coordinates
    SCREAMING_SNAKE_CASE__         =    np.stack(
        np.meshgrid(np.arange(0			,							image.shape[1]						)			,							np.arange(0			,							image.shape[0]						)						)			,							2						)
    SCREAMING_SNAKE_CASE__         =    np.round(grid - flow						).astype(np.intaa						)

    # Find the locations outside of the original image
    SCREAMING_SNAKE_CASE__         =    (grid < 0) | (grid >= np.array([image.shape[1], image.shape[0]]						))
    SCREAMING_SNAKE_CASE__         =    0

    SCREAMING_SNAKE_CASE__         =    image[grid[:, :, 1], grid[:, :, 0]]

    # Set pixels at invalid locations to 0
    SCREAMING_SNAKE_CASE__         =    0

    return warped





def 				__a							(       __A			,							__A			,							__A			,							__A = None			,							):
    if alpha is None:
        SCREAMING_SNAKE_CASE__         =    0.1

    # Initialize flow
    SCREAMING_SNAKE_CASE__         =    np.zeros_like(__A						)
    SCREAMING_SNAKE_CASE__         =    np.zeros_like(__A						)

    # Prepare kernels for the calculation of the derivatives and the average velocity
    SCREAMING_SNAKE_CASE__         =    np.array([[-1, 1], [-1, 1]]						) * 0.25
    SCREAMING_SNAKE_CASE__         =    np.array([[-1, -1], [1, 1]]						) * 0.25
    SCREAMING_SNAKE_CASE__         =    np.array([[1, 1], [1, 1]]						) * 0.25
    SCREAMING_SNAKE_CASE__         =    np.array(
        [[1 / 12, 1 / 6, 1 / 12], [1 / 6, 0, 1 / 6], [1 / 12, 1 / 6, 1 / 12]]						)

    # Iteratively refine the flow
    for _ in range(__A						):
        SCREAMING_SNAKE_CASE__         =    warp(__A			,							__A			,							__A						)
        SCREAMING_SNAKE_CASE__         =    convolve(__A			,							__A						) + convolve(__A			,							__A						)
        SCREAMING_SNAKE_CASE__         =    convolve(__A			,							__A						) + convolve(__A			,							__A						)
        SCREAMING_SNAKE_CASE__         =    convolve(__A			,							__A						) + convolve(__A			,							-kernel_t						)

        SCREAMING_SNAKE_CASE__         =    convolve(__A			,							__A						)
        SCREAMING_SNAKE_CASE__         =    convolve(__A			,							__A						)

        # This updates the flow as proposed in the paper (Step 12)
        SCREAMING_SNAKE_CASE__         =    (
            derivative_x * avg_horizontal_velocity
            + derivative_y * avg_vertical_velocity
            + derivative_t
        )
        SCREAMING_SNAKE_CASE__         =    update / (alpha**2 + derivative_x**2 + derivative_y**2)

        SCREAMING_SNAKE_CASE__         =    avg_horizontal_velocity - derivative_x * update
        SCREAMING_SNAKE_CASE__         =    avg_vertical_velocity - derivative_y * update

    return horizontal_flow, vertical_flow


if __name__ == "__main__":
  import doctest

  doctest.testmod()


