


class 	_lowercase				:






				'''simple docstring'''



				def __init__(	self      :Any      ,      lowerCAmelCase__      :Optional[Any]     )		->      Optional[int]:
										__SCREAMING_SNAKE_CASE						:					int		      =		data
										__SCREAMING_SNAKE_CASE						:					Optional[int]		      =		None
										__SCREAMING_SNAKE_CASE						:					List[str]		      =		None



				def __str__(	self      :Tuple     )		->      List[str]:
										return f'''{self.data}'''




class 	_lowercase				:






				'''simple docstring'''



				def __init__(	self      :Tuple     )		->      int:
										__SCREAMING_SNAKE_CASE						:					List[str]		      =		None
										__SCREAMING_SNAKE_CASE						:					Any		      =		None


				def __iter__(	self      :int     )		->      Optional[Any]:
										__SCREAMING_SNAKE_CASE						:					List[str]		      =		self.head
										while node:
																yield node.data
																__SCREAMING_SNAKE_CASE						:					Optional[int]		      =		node.next


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


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


				def 		__magic_name__(	self      :Optional[int]      ,      lowerCAmelCase__      :List[Any]     )		->      Tuple:
										self.insert_at_nth(0      ,      lowerCAmelCase__     )


				def 		__magic_name__(	self      :Optional[Any]      ,      lowerCAmelCase__      :int     )		->      str:
										self.insert_at_nth(len(self     )      ,      lowerCAmelCase__     )


				def 		__magic_name__(	self      :Optional[Any]      ,      lowerCAmelCase__      :int      ,      lowerCAmelCase__      :Any     )		->      List[str]:
										__SCREAMING_SNAKE_CASE						:					Any		      =		len(self     )

										if not 0 <= index <= length:
																raise IndexError('''list index out of range'''     )
										__SCREAMING_SNAKE_CASE						:					List[Any]		      =		Node(lowerCAmelCase__     )
										if self.head is None:
																__SCREAMING_SNAKE_CASE						:					Any		      =		new_node
										elif index == 0:
																__SCREAMING_SNAKE_CASE						:					int		      =		new_node
																__SCREAMING_SNAKE_CASE						:					Any		      =		self.head
																__SCREAMING_SNAKE_CASE						:					Union[str, Any]		      =		new_node
										elif index == length:
																__SCREAMING_SNAKE_CASE						:					List[Any]		      =		new_node
																__SCREAMING_SNAKE_CASE						:					List[Any]		      =		self.tail
																__SCREAMING_SNAKE_CASE						:					Union[str, Any]		      =		new_node
										else:
																__SCREAMING_SNAKE_CASE						:					int		      =		self.head
																for _ in range(0      ,      lowerCAmelCase__     ):
																						__SCREAMING_SNAKE_CASE						:					Optional[Any]		      =		temp.next
																__SCREAMING_SNAKE_CASE						:					int		      =		new_node
																__SCREAMING_SNAKE_CASE						:					str		      =		temp.previous
																__SCREAMING_SNAKE_CASE						:					List[str]		      =		temp
																__SCREAMING_SNAKE_CASE						:					str		      =		new_node


				def 		__magic_name__(	self      :Any     )		->      Union[str, Any]:
										return self.delete_at_nth(0     )


				def 		__magic_name__(	self      :Optional[Any]     )		->      Union[str, Any]:
										return self.delete_at_nth(len(self     ) - 1     )


				def 		__magic_name__(	self      :Any      ,      lowerCAmelCase__      :int     )		->      Optional[int]:
										__SCREAMING_SNAKE_CASE						:					List[str]		      =		len(self     )

										if not 0 <= index <= length - 1:
																raise IndexError('''list index out of range'''     )
										__SCREAMING_SNAKE_CASE						:					Optional[Any]		      =		self.head  # default first node
										if length == 1:
																__SCREAMING_SNAKE_CASE						:					Any		      =		None
										elif index == 0:
																__SCREAMING_SNAKE_CASE						:					Optional[Any]		      =		self.head.next
																__SCREAMING_SNAKE_CASE						:					List[str]		      =		None
										elif index == length - 1:
																__SCREAMING_SNAKE_CASE						:					Union[str, Any]		      =		self.tail
																__SCREAMING_SNAKE_CASE						:					List[str]		      =		self.tail.previous
																__SCREAMING_SNAKE_CASE						:					Dict		      =		None
										else:
																__SCREAMING_SNAKE_CASE						:					Dict		      =		self.head
																for _ in range(0      ,      lowerCAmelCase__     ):
																						__SCREAMING_SNAKE_CASE						:					Union[str, Any]		      =		temp.next
																__SCREAMING_SNAKE_CASE						:					str		      =		temp
																__SCREAMING_SNAKE_CASE						:					int		      =		temp.previous
																__SCREAMING_SNAKE_CASE						:					Optional[int]		      =		temp.next
										return delete_node.data


				def 		__magic_name__(	self      :Dict      ,      lowerCAmelCase__      :List[str]     )		->      str:
										__SCREAMING_SNAKE_CASE						:					Union[str, Any]		      =		self.head

										while current.data != data:  # Find the position to delete
																if current.next:
																						__SCREAMING_SNAKE_CASE						:					int		      =		current.next
																else:  # We have reached the end an no value matches
																						raise ValueError('''No data matching given value'''     )

										if current == self.head:
																self.delete_head()

										elif current == self.tail:
																self.delete_tail()

										else:  # Before: 1 <--> 2(current) <--> 3
																__SCREAMING_SNAKE_CASE						:					Optional[Any]		      =		current.next  # 1 --> 3
																__SCREAMING_SNAKE_CASE						:					Union[str, Any]		      =		current.previous  # 1 <--> 3
										return data



				def 		__magic_name__(	self      :str     )		->      Any:
										return len(self     ) == 0




def 	_UpperCamelCase							(				):
						__SCREAMING_SNAKE_CASE						:					Tuple		      =		DoublyLinkedList()
						assert linked_list.is_empty() is True
						assert str(lowercase__				) == ""

						try:
												linked_list.delete_head()
												raise AssertionError  # This should not happen.
						except IndexError:
												assert True  # This should happen.

						try:
												linked_list.delete_tail()
												raise AssertionError  # This should not happen.
						except IndexError:
												assert True  # This should happen.

						for i in range(10				):
												assert len(lowercase__				) == i
												linked_list.insert_at_nth(lowercase__   ,	i + 1				)
						assert str(lowercase__				) == "->".join(str(lowercase__				) for i in range(1   ,	11				)				)

						linked_list.insert_at_head(0				)
						linked_list.insert_at_tail(11				)
						assert str(lowercase__				) == "->".join(str(lowercase__				) for i in range(0   ,	12				)				)

						assert linked_list.delete_head() == 0
						assert linked_list.delete_at_nth(9				) == 10
						assert linked_list.delete_tail() == 11
						assert len(lowercase__				) == 9
						assert str(lowercase__				) == "->".join(str(lowercase__				) for i in range(1   ,	10				)				)


if __name__ == "__main__":
						from doctest import testmod

						testmod()




from __future__ import annotations


def 	_UpperCamelCase							(				lowercase__				):
						__SCREAMING_SNAKE_CASE						:					List[Any]		      =		sorted(lowercase__				)
						__SCREAMING_SNAKE_CASE						:					str		      =		len(lowercase__				)
						__SCREAMING_SNAKE_CASE						:					Union[str, Any]		      =		length >> 1
						return (
						    (sorted_list[mid_index] + sorted_list[mid_index - 1]) / 2
						    if length % 2 == 0
						    else sorted_list[mid_index]
						)


def 	_UpperCamelCase							(				):
						import doctest

						doctest.testmod()


if __name__ == "__main__":
						main()
