





def     __UpperCamelCase						(_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	)       ->     List[Any]:
  lowercase__			    =						0
  lowercase__			    =						len(_SCREAMING_SNAKE_CASE	) - 1

  while left <= right:
    # avoid divided by 0 during interpolation
    if sorted_collection[left] == sorted_collection[right]:
      if sorted_collection[left] == item:
        return left
      else:
        return None

    lowercase__			    =						left + ((item - sorted_collection[left]) * (right - left)) // (
        sorted_collection[right] - sorted_collection[left]
    )

    # out of range check
    if point < 0 or point >= len(_SCREAMING_SNAKE_CASE	):
      return None

    lowercase__			    =						sorted_collection[point]
    if current_item == item:
      return point
    else:
      if point < left:
        lowercase__			    =						left
        lowercase__			    =						point
      elif point > right:
        lowercase__			    =						right
        lowercase__			    =						point
      else:
        if item < current_item:
          lowercase__			    =						point - 1
        else:
          lowercase__			    =						point + 1
  return None




def     __UpperCamelCase						(_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	)       ->     Optional[int]:

  # avoid divided by 0 during interpolation
  if sorted_collection[left] == sorted_collection[right]:
    if sorted_collection[left] == item:
      return left
    else:
      return None

  lowercase__			    =						left + ((item - sorted_collection[left]) * (right - left)) // (
      sorted_collection[right] - sorted_collection[left]
  )

  # out of range check
  if point < 0 or point >= len(_SCREAMING_SNAKE_CASE	):
    return None

  if sorted_collection[point] == item:
    return point
  elif point < left:
    return interpolation_search_by_recursion(_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	)
  elif point > right:
    return interpolation_search_by_recursion(_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	)
  else:
    if sorted_collection[point] > item:
      return interpolation_search_by_recursion(
          _SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	,		point - 1	)
    else:
      return interpolation_search_by_recursion(
          _SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	,		point + 1	,		_SCREAMING_SNAKE_CASE	)




def     __UpperCamelCase						(_SCREAMING_SNAKE_CASE	)       ->     Optional[Any]:
  if collection != sorted(_SCREAMING_SNAKE_CASE	):
    raise ValueError('Collection must be ascending sorted'	)
  return True


if __name__ == "__main__":
      import sys
      lowercase_					     =	0
      if debug == 1:
            lowercase_					     =	[10, 30, 40, 45, 50, 66, 77, 93]
            try:
                  __assert_sorted(collection)
            except ValueError:
                  sys.exit("""Sequence must be ascending sorted to apply interpolation search""")
            lowercase_					     =	67

      lowercase_					     =	interpolation_search(collection, target)
      if result is not None:
            print(f'''{target} found at positions: {result}''')
      else:
            print("""Not found""")









def     __UpperCamelCase						(_SCREAMING_SNAKE_CASE = 50	)       ->     int:
  lowercase__			    =						[1] * (length + 1)

  for row_length in range(3	,		length + 1	):
    for block_length in range(3	,		row_length + 1	):
      for block_start in range(row_length - block_length	):
        ways_number[row_length] += ways_number[
            row_length - block_start - block_length - 1
        ]

      ways_number[row_length] += 1

  return ways_number[length]


if __name__ == "__main__":
      print(f'''{solution() = }''')


