






'''simple docstring'''
from __future__ import annotations

from collections.abc import Iterable, Iterator
from dataclasses import dataclass

a_					= (3, 9, -1_1, 0, 7, 5, 1, -1)
a_					= (4, 6, 2, 0, 8, 1_0, 3, -2)






@dataclass
class      __SCREAMING_SNAKE_CASE      :
 snake_case_  							=							42
 snake_case_  							=							42






class      __SCREAMING_SNAKE_CASE      :




 def __init__(      self	:							List[Any]					,      __lowercase	:							Iterable[int]      )	->						None:
       SCREAMING_SNAKE_CASE__     :				Node | None									=None
       for i in sorted(__lowercase					,      reverse=__lowercase      ):
             SCREAMING_SNAKE_CASE__     :				Any									=Node(__lowercase					,      self.head      )




 def __iter__(      self	:							Any      )	->						Iterator[int]:
       SCREAMING_SNAKE_CASE__     :				List[Any]									=self.head
       while node:
             yield node.data
             SCREAMING_SNAKE_CASE__     :				Any									=node.next_node




 def __len__(      self	:							List[Any]      )	->						int:
       return sum(1 for _ in self      )




 def __str__(      self	:							List[Any]      )	->						str:
       return " -> ".join([str(__lowercase      ) for node in self]      )





def  _a(  UpperCamelCase__				:						SortedLinkedList,	UpperCamelCase__				:						SortedLinkedList							):




      '''simple docstring'''






      return SortedLinkedList(list(UpperCamelCase__							) + list(UpperCamelCase__							)							)


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  a_					= SortedLinkedList
  print(merge_lists(SSL(test_data_odd), SSL(test_data_even)))







'''simple docstring'''
def  _a(  UpperCamelCase__				:						Optional[int],	UpperCamelCase__				:						int							):




      '''simple docstring'''






      SCREAMING_SNAKE_CASE__     :				Optional[int]									=0
      SCREAMING_SNAKE_CASE__     :				Union[str, Any]									=len(UpperCamelCase__							) - 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

            SCREAMING_SNAKE_CASE__     :				Union[str, Any]									=left + ((item - sorted_collection[left]) * (right - left)) // (
                sorted_collection[right] - sorted_collection[left]
            )

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

            SCREAMING_SNAKE_CASE__     :				Optional[int]									=sorted_collection[point]
            if current_item == item:
                  return point
            else:
                  if point < left:
                        SCREAMING_SNAKE_CASE__     :				Union[str, Any]									=left
                        SCREAMING_SNAKE_CASE__     :				Optional[Any]									=point
                  elif point > right:
                        SCREAMING_SNAKE_CASE__     :				Optional[int]									=right
                        SCREAMING_SNAKE_CASE__     :				Tuple									=point
                  else:
                        if item < current_item:
                              SCREAMING_SNAKE_CASE__     :				str									=point - 1
                        else:
                              SCREAMING_SNAKE_CASE__     :				Tuple									=point + 1
      return None





def  _a(  UpperCamelCase__				:						List[str],	UpperCamelCase__				:						Optional[Any],	UpperCamelCase__				:						Union[str, Any],	UpperCamelCase__				:						Union[str, Any]							):




      '''simple docstring'''






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

      SCREAMING_SNAKE_CASE__     :				Dict									=left + ((item - sorted_collection[left]) * (right - left)) // (
          sorted_collection[right] - sorted_collection[left]
      )

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

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





def  _a(  UpperCamelCase__				:						Dict							):




      '''simple docstring'''






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


if __name__ == "__main__":
  import sys
  a_					= 0
  if debug == 1:
    a_					= [1_0, 3_0, 4_0, 4_5, 5_0, 6_6, 7_7, 9_3]
    try:
      __assert_sorted(collection)
    except ValueError:
      sys.exit('Sequence must be ascending sorted to apply interpolation search')
    a_					= 6_7

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