


def 	__lowerCAmelCase   (SCREAMING_SNAKE_CASE , SCREAMING_SNAKE_CASE )->  Union[str, Any]:




      """simple docstring"""

      snake_case_	=				0
      snake_case_	=				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

            snake_case_	=				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

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






def 	__lowerCAmelCase   (SCREAMING_SNAKE_CASE , SCREAMING_SNAKE_CASE , SCREAMING_SNAKE_CASE , SCREAMING_SNAKE_CASE )->  Any:




      """simple docstring"""

      if sorted_collection[left] == sorted_collection[right]:
            if sorted_collection[left] == item:
                  return left
            else:
                  return None

      snake_case_	=				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 	__lowerCAmelCase   (SCREAMING_SNAKE_CASE )->  Union[str, Any]:




      """simple docstring"""

      if collection != sorted(SCREAMING_SNAKE_CASE ):
            raise ValueError('''Collection must be ascending sorted''' )
      return True


if __name__ == "__main__":
   import sys
   UpperCAmelCase      =   0
   if debug == 1:
      UpperCAmelCase      =   [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""")
      UpperCAmelCase      =   67

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



def 	__lowerCAmelCase   (SCREAMING_SNAKE_CASE , SCREAMING_SNAKE_CASE )->  list[int]:




      """simple docstring"""

      snake_case_	=				int(SCREAMING_SNAKE_CASE )

      # Initialize Result
      snake_case_	=				[]

      # Traverse through all denomination
      for denomination in reversed(SCREAMING_SNAKE_CASE ):
            # Find denominations
            while int(SCREAMING_SNAKE_CASE ) >= int(SCREAMING_SNAKE_CASE ):
                  total_value -= int(SCREAMING_SNAKE_CASE )
                  answer.append(SCREAMING_SNAKE_CASE )  # Append the "answers" array

      return answer


# Driver Code
if __name__ == "__main__":
   UpperCAmelCase      =   []
   UpperCAmelCase      =   """0"""

   if (
       input("""Do you want to enter your denominations ? (yY/n): """).strip().lower()
       == "y"
   ):
      UpperCAmelCase      =   int(input("""Enter the number of denominations you want to add: """).strip())

      for i in range(0, n):
         denominations.append(int(input(f'''Denomination {i}: ''').strip()))
      UpperCAmelCase      =   input("""Enter the change you want to make in Indian Currency: """).strip()
   else:
      # All denominations of Indian Currency if user does not enter
      UpperCAmelCase      =   [1, 2, 5, 10, 20, 50, 100, 500, 2000]
      UpperCAmelCase      =   input("""Enter the change you want to make: """).strip()

   if int(value) == 0 or int(value) < 0:
      print("""The total value cannot be zero or negative.""")

   else:
      print(f'''Following is minimal change for {value}: ''')
      UpperCAmelCase      =   find_minimum_change(denominations, value)
      # Print result
      for i in range(len(answer)):
         print(answer[i], end=""" """)