


from __future__ import annotations

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

__lowerCAmelCase	: Dict  				=(3, 9, -1_1, 0, 7, 5, 1, -1)
__lowerCAmelCase	: int  				=(4, 6, 2, 0, 8, 1_0, 3, -2)
@dataclass
class        _lowercase      :






				'''simple docstring'''



				SCREAMING_SNAKE_CASE__				:			int
				SCREAMING_SNAKE_CASE__				:			Node | None




class        _lowercase      :






				'''simple docstring'''



				def __init__(       self			:str			,			lowerCAmelCase__			:Iterable[int]	)		->			None:
										__SCREAMING_SNAKE_CASE						:     Node | None					=		None
										for i in sorted(lowerCAmelCase__			,			reverse=lowerCAmelCase__	):
																__SCREAMING_SNAKE_CASE						:     int					=		Node(lowerCAmelCase__			,			self.head	)


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


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



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




def        _UpperCamelCase							(      lowercase__    ,       lowercase__      ):
						return SortedLinkedList(list(lowercase__      ) + list(lowercase__      )      )


if __name__ == "__main__":
						import doctest

						doctest.testmod()
						__lowerCAmelCase	: Union[str, Any]  				=SortedLinkedList
						print(merge_lists(SSL(test_data_odd), SSL(test_data_even)))




from __future__ import annotations

import bisect


def        _UpperCamelCase							(      lowercase__    ,       lowercase__    ,       lowercase__ = 0    ,       lowercase__ = -1      ):
						if hi < 0:
												__SCREAMING_SNAKE_CASE						:     Union[str, Any]					=		len(lowercase__      )

						while lo < hi:
												__SCREAMING_SNAKE_CASE						:     Any					=		lo + (hi - lo) // 2
												if sorted_collection[mid] < item:
																		__SCREAMING_SNAKE_CASE						:     Union[str, Any]					=		mid + 1
												else:
																		__SCREAMING_SNAKE_CASE						:     Optional[Any]					=		mid

						return lo


def        _UpperCamelCase							(      lowercase__    ,       lowercase__    ,       lowercase__ = 0    ,       lowercase__ = -1      ):
						if hi < 0:
												__SCREAMING_SNAKE_CASE						:     List[Any]					=		len(lowercase__      )

						while lo < hi:
												__SCREAMING_SNAKE_CASE						:     Optional[int]					=		lo + (hi - lo) // 2
												if sorted_collection[mid] <= item:
																		__SCREAMING_SNAKE_CASE						:     Any					=		mid + 1
												else:
																		__SCREAMING_SNAKE_CASE						:     Optional[int]					=		mid

						return lo


def        _UpperCamelCase							(      lowercase__    ,       lowercase__    ,       lowercase__ = 0    ,       lowercase__ = -1      ):
						sorted_collection.insert(bisect_left(lowercase__    ,       lowercase__    ,       lowercase__    ,       lowercase__      )    ,       lowercase__      )


def        _UpperCamelCase							(      lowercase__    ,       lowercase__    ,       lowercase__ = 0    ,       lowercase__ = -1      ):
						sorted_collection.insert(bisect_right(lowercase__    ,       lowercase__    ,       lowercase__    ,       lowercase__      )    ,       lowercase__      )


def        _UpperCamelCase							(      lowercase__    ,       lowercase__      ):
						__SCREAMING_SNAKE_CASE						:     Any					=		0
						__SCREAMING_SNAKE_CASE						:     List[Any]					=		len(lowercase__      ) - 1

						while left <= right:
												__SCREAMING_SNAKE_CASE						:     str					=		left + (right - left) // 2
												__SCREAMING_SNAKE_CASE						:     List[str]					=		sorted_collection[midpoint]
												if current_item == item:
																		return midpoint
												elif item < current_item:
																		__SCREAMING_SNAKE_CASE						:     int					=		midpoint - 1
												else:
																		__SCREAMING_SNAKE_CASE						:     Dict					=		midpoint + 1
						return None


def        _UpperCamelCase							(      lowercase__    ,       lowercase__      ):
						__SCREAMING_SNAKE_CASE						:     Union[str, Any]					=		bisect.bisect_left(lowercase__    ,       lowercase__      )
						if index != len(lowercase__      ) and sorted_collection[index] == item:
												return index
						return None


def        _UpperCamelCase							(      lowercase__    ,       lowercase__    ,       lowercase__    ,       lowercase__      ):
						if right < left:
												return None

						__SCREAMING_SNAKE_CASE						:     int					=		left + (right - left) // 2

						if sorted_collection[midpoint] == item:
												return midpoint
						elif sorted_collection[midpoint] > item:
												return binary_search_by_recursion(lowercase__    ,       lowercase__    ,       lowercase__    ,       midpoint - 1      )
						else:
												return binary_search_by_recursion(lowercase__    ,       lowercase__    ,       midpoint + 1    ,       lowercase__      )


if __name__ == "__main__":
						__lowerCAmelCase	: Dict  				=input('Enter numbers separated by comma:\n').strip()
						__lowerCAmelCase	: str  				=sorted(int(item) for item in user_input.split(','))
						__lowerCAmelCase	: Tuple  				=int(input('Enter a single number to be found in the list:\n'))
						__lowerCAmelCase	: Tuple  				=binary_search(collection, target)
						if result is None:
												print(f"""{target} was not found in {collection}.""")
						else:
												print(f"""{target} was found at position {result} in {collection}.""")
