


class 				snake_case__:







						'''simple docstring'''




						def __init__(				self   ,						__lowercase   ,						__lowercase							)					->    List[Any]:
										lowerCAmelCase_ :      Optional[Any]    				=				name
										lowerCAmelCase_ :      str    				=				val




						def __str__(				self							)					->    Dict:
										return f"""{self.__class__.__name__}({self.name}, {self.val})"""




						def __lt__(				self   ,						__lowercase							)					->    Tuple:
										return self.val < other.val







class 				snake_case__:







						'''simple docstring'''




						def __init__(				self   ,						__lowercase							)					->    Optional[int]:
										lowerCAmelCase_ :      List[Any]    				=				{}
										lowerCAmelCase_ :      Dict    				=				{}
										lowerCAmelCase_ :      str    				=				self.build_heap(_lowercase							)




						def __getitem__(				self   ,						__lowercase							)					->    List[Any]:
										return self.get_value(_lowercase							)




						def 						lowercase_ (				self   ,						__lowercase							)					->    Optional[int]:
										return (idx - 1) // 2




						def 						lowercase_ (				self   ,						__lowercase							)					->    Any:
										return idx * 2 + 1




						def 						lowercase_ (				self   ,						__lowercase							)					->    List[Any]:
										return idx * 2 + 2




						def 						lowercase_ (				self   ,						__lowercase							)					->    Optional[int]:
										return self.heap_dict[key]




						def 						lowercase_ (				self   ,						__lowercase							)					->    Optional[int]:
										lowerCAmelCase_ :      int    				=				len(_lowercase							) - 1
										lowerCAmelCase_ :      Optional[int]    				=				self.get_parent_idx(_lowercase							)

										for idx, i in enumerate(_lowercase							):
														lowerCAmelCase_ :      Dict    				=				idx
														lowerCAmelCase_ :      Optional[int]    				=				i.val

										for i in range(_lowercase   ,						-1   ,						-1							):
														self.sift_down(_lowercase   ,						_lowercase							)
										return array




						def 						lowercase_ (				self   ,						__lowercase   ,						__lowercase							)					->    Tuple:

										while True:
														lowerCAmelCase_ :      Optional[int]    				=				self.get_left_child_idx(_lowercase							)  # noqa: E741
														lowerCAmelCase_ :      Optional[Any]    				=				self.get_right_child_idx(_lowercase							)

														lowerCAmelCase_ :      Union[str, Any]    				=				idx
														if l < len(_lowercase							) and array[l] < array[idx]:
																		lowerCAmelCase_ :      Dict    				=				l
														if r < len(_lowercase							) and array[r] < array[smallest]:
																		lowerCAmelCase_ :      str    				=				r

														if smallest != idx:
																		lowerCAmelCase_ :      str    				=				array[smallest], array[idx]
																		(
																		    lowerCAmelCase_		
																		) :      List[str]    				=				(
																		    self.idx_of_element[array[smallest]],
																		    self.idx_of_element[array[idx]],
																		)
																		lowerCAmelCase_ :      List[Any]    				=				smallest
														else:
																		break




						def 						lowercase_ (				self   ,						__lowercase							)					->    str:
										lowerCAmelCase_ :      Union[str, Any]    				=				self.get_parent_idx(_lowercase							)
										while p >= 0 and self.heap[p] > self.heap[idx]:
														lowerCAmelCase_ :      Dict    				=				self.heap[idx], self.heap[p]
														lowerCAmelCase_ :      str    				=				(
														    self.idx_of_element[self.heap[idx]],
														    self.idx_of_element[self.heap[p]],
														)
														lowerCAmelCase_ :      Union[str, Any]    				=				p
														lowerCAmelCase_ :      Any    				=				self.get_parent_idx(_lowercase							)




						def 						lowercase_ (				self							)					->    str:
										return self.heap[0]




						def 						lowercase_ (				self							)					->    Any:
										lowerCAmelCase_ :      List[str]    				=				self.heap[-1], self.heap[0]
										lowerCAmelCase_ :      List[str]    				=				(
										    self.idx_of_element[self.heap[-1]],
										    self.idx_of_element[self.heap[0]],
										)

										lowerCAmelCase_ :      Optional[int]    				=				self.heap.pop()
										del self.idx_of_element[x]
										self.sift_down(0   ,						self.heap							)
										return x




						def 						lowercase_ (				self   ,						__lowercase							)					->    int:
										self.heap.append(_lowercase							)
										lowerCAmelCase_ :      Optional[int]    				=				len(self.heap							) - 1
										lowerCAmelCase_ :      int    				=				node.val
										self.sift_up(len(self.heap							) - 1							)




						def 						lowercase_ (				self							)					->    int:
										return len(self.heap							) == 0




						def 						lowercase_ (				self   ,						__lowercase   ,						__lowercase							)					->    Optional[int]:
										assert (
										    self.heap[self.idx_of_element[node]].val > new_value
										), "newValue must be less that current value"
										lowerCAmelCase_ :      List[Any]    				=				new_value
										lowerCAmelCase_ :      Any    				=				new_value
										self.sift_up(self.idx_of_element[node]							)






_UpperCAmelCase			:  Any     =Node("""R""", -1)
_UpperCAmelCase			:  List[Any]     =Node("""B""", 6)
_UpperCAmelCase			:  Union[str, Any]     =Node("""A""", 3)
_UpperCAmelCase			:  Any     =Node("""X""", 1)
_UpperCAmelCase			:  Tuple     =Node("""E""", 4)

# Use one of these two ways to generate Min-Heap

# Generating Min-Heap from array
_UpperCAmelCase			:  List[str]     =MinHeap([r, b, a, x, e])

# Generating Min-Heap by Insert method
# myMinHeap.insert(a)
# myMinHeap.insert(b)
# myMinHeap.insert(x)
# myMinHeap.insert(r)
# myMinHeap.insert(e)

# Before
print("""Min Heap - before decrease key""")
for i in my_min_heap.heap:
						print(i)

print("""Min Heap - After decrease key of node [B -> -17]""")
my_min_heap.decrease_key(b, -17)

# After
for i in my_min_heap.heap:
						print(i)

if __name__ == "__main__":
						import doctest

						doctest.testmod()



from __future__ import annotations

# This is the precision for this function which can be altered.
# It is recommended for users to keep this number greater than or equal to 10.
_UpperCAmelCase			:  Tuple     =10



def 			lowerCAmelCase (		lowerCAmelCase_ ,   lowerCAmelCase_ ,   lowerCAmelCase_ ,   lowerCAmelCase_ )-> int:
				for i in range(lowerCAmelCase_ ,   lowerCAmelCase_ ):
								if array[i] == target:
												return i
				return -1



def 			lowerCAmelCase (		lowerCAmelCase_ ,   lowerCAmelCase_ )-> int:
				lowerCAmelCase_ :      Any    				=				0
				lowerCAmelCase_ :      int    				=				len(lowerCAmelCase_ )
				while left <= right:
								if right - left < precision:
												return lin_search(lowerCAmelCase_ ,   lowerCAmelCase_ ,   lowerCAmelCase_ ,   lowerCAmelCase_ )

								lowerCAmelCase_ :      List[Any]    				=				(left + right) // 3 + 1
								lowerCAmelCase_ :      List[str]    				=				2 * (left + right) // 3 + 1

								if array[one_third] == target:
												return one_third
								elif array[two_third] == target:
												return two_third

								elif target < array[one_third]:
												lowerCAmelCase_ :      Dict    				=				one_third - 1
								elif array[two_third] < target:
												lowerCAmelCase_ :      List[Any]    				=				two_third + 1

								else:
												lowerCAmelCase_ :      Union[str, Any]    				=				one_third + 1
												lowerCAmelCase_ :      Tuple    				=				two_third - 1
				else:
								return -1



def 			lowerCAmelCase (		lowerCAmelCase_ ,   lowerCAmelCase_ ,   lowerCAmelCase_ ,   lowerCAmelCase_ )-> int:
				if left < right:
								if right - left < precision:
												return lin_search(lowerCAmelCase_ ,   lowerCAmelCase_ ,   lowerCAmelCase_ ,   lowerCAmelCase_ )
								lowerCAmelCase_ :      Union[str, Any]    				=				(left + right) // 3 + 1
								lowerCAmelCase_ :      Optional[int]    				=				2 * (left + right) // 3 + 1

								if array[one_third] == target:
												return one_third
								elif array[two_third] == target:
												return two_third

								elif target < array[one_third]:
												return rec_ternary_search(lowerCAmelCase_ ,   one_third - 1 ,   lowerCAmelCase_ ,   lowerCAmelCase_ )
								elif array[two_third] < target:
												return rec_ternary_search(two_third + 1 ,   lowerCAmelCase_ ,   lowerCAmelCase_ ,   lowerCAmelCase_ )
								else:
												return rec_ternary_search(one_third + 1 ,   two_third - 1 ,   lowerCAmelCase_ ,   lowerCAmelCase_ )
				else:
								return -1


if __name__ == "__main__":
						import doctest

						doctest.testmod()

						_UpperCAmelCase			:  Tuple     =input("""Enter numbers separated by comma:\n""").strip()
						_UpperCAmelCase			:  Union[str, Any]     =[int(item.strip()) for item in user_input.split(""",""")]
						assert collection == sorted(collection), f"List must be ordered.\n{collection}."
						_UpperCAmelCase			:  int     =int(input("""Enter the number to be found in the list:\n""").strip())
						_UpperCAmelCase			:  Optional[Any]     =ite_ternary_search(collection, target)
						_UpperCAmelCase			:  List[str]     =rec_ternary_search(0, len(collection) - 1, collection, target)
						if resulta != -1:
												print(f"""Iterative search: {target} found at positions: {resulta}""")
												print(f"""Recursive search: {target} found at positions: {resulta}""")
						else:
												print("""Not found""")