



"""simple docstring"""

class  __lowercase  :







						"""simple docstring"""







						def __init__(self ,		lowercase__ ,		lowercase__							):
											snake_case_       :		Union[str, Any]			       =       name
											snake_case_       :		List[str]			       =       val







						def __str__(self							):
											return f'{self.__class__.__name__}({self.name}, {self.val})'







						def __lt__(self ,		lowercase__							):
											return self.val < other.val







class  __lowercase  :







						"""simple docstring"""







						def __init__(self ,		lowercase__							):
											snake_case_       :		Dict			       =       {}
											snake_case_       :		int			       =       {}
											snake_case_       :		Tuple			       =       self.build_heap(lowerCamelCase_							)







						def __getitem__(self ,		lowercase__							):
											return self.get_value(lowerCamelCase_							)







						def     __UpperCamelCase				(self ,		lowercase__							):
											return (idx - 1) // 2







						def     __UpperCamelCase				(self ,		lowercase__							):
											return idx * 2 + 1







						def     __UpperCamelCase				(self ,		lowercase__							):
											return idx * 2 + 2







						def     __UpperCamelCase				(self ,		lowercase__							):
											return self.heap_dict[key]







						def     __UpperCamelCase				(self ,		lowercase__							):
											snake_case_       :		str			       =       len(lowerCamelCase_							) - 1
											snake_case_       :		str			       =       self.get_parent_idx(lowerCamelCase_							)

											for idx, i in enumerate(lowerCamelCase_							):
																snake_case_       :		int			       =       idx
																snake_case_       :		List[str]			       =       i.val

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







						def     __UpperCamelCase				(self ,		lowercase__ ,		lowercase__							):
											while True:
																snake_case_       :		Union[str, Any]			       =       self.get_left_child_idx(lowerCamelCase_							)  # noqa: E741
																snake_case_       :		Optional[int]			       =       self.get_right_child_idx(lowerCamelCase_							)

																snake_case_       :		List[str]			       =       idx
																if l < len(lowerCamelCase_							) and array[l] < array[idx]:
																					snake_case_       :		str			       =       l
																if r < len(lowerCamelCase_							) and array[r] < array[smallest]:
																					snake_case_       :		Optional[Any]			       =       r

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







						def     __UpperCamelCase				(self ,		lowercase__							):
											snake_case_       :		List[str]			       =       self.get_parent_idx(lowerCamelCase_							)
											while p >= 0 and self.heap[p] > self.heap[idx]:
																snake_case_       ,      snake_case_       :		Tuple			       =       self.heap[idx], self.heap[p]
																snake_case_       ,      snake_case_       :		Optional[int]			       =       (
																    self.idx_of_element[self.heap[idx]],
																    self.idx_of_element[self.heap[p]],
																)
																snake_case_       :		List[Any]			       =       p
																snake_case_       :		List[str]			       =       self.get_parent_idx(lowerCamelCase_							)







						def     __UpperCamelCase				(self							):
											return self.heap[0]







						def     __UpperCamelCase				(self							):
											snake_case_       ,      snake_case_       :		Tuple			       =       self.heap[-1], self.heap[0]
											snake_case_       ,      snake_case_       :		List[Any]			       =       (
											    self.idx_of_element[self.heap[-1]],
											    self.idx_of_element[self.heap[0]],
											)

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







						def     __UpperCamelCase				(self ,		lowercase__							):
											self.heap.append(lowerCamelCase_							)
											snake_case_       :		Dict			       =       len(self.heap							) - 1
											snake_case_       :		Optional[int]			       =       node.val
											self.sift_up(len(self.heap							) - 1							)







						def     __UpperCamelCase				(self							):
											return len(self.heap							) == 0







						def     __UpperCamelCase				(self ,		lowercase__ ,		lowercase__							):
											assert (
											    self.heap[self.idx_of_element[node]].val > new_value
											), "newValue must be less that current value"
											snake_case_       :		Tuple			       =       new_value
											snake_case_       :		Optional[int]			       =       new_value
											self.sift_up(self.idx_of_element[node]							)
a_       =       Node('''R''', -1)
a_       =       Node('''B''', 6)
a_       =       Node('''A''', 3)
a_       =       Node('''X''', 1)
a_       =       Node('''E''', 4)

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

# Generating Min-Heap from array
a_       =       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()








'''simple docstring'''






from __future__ import annotations


def    _snake_case  (	A			)		->       bool:
							lowerCAmelCase__			  =      str(A			)
							return len(A			) == 9 and set(A			) == set('''123456789'''			)


def    _snake_case  (	)		->       int | None:
							for base_num in range(9999					,       4999					,       -1			):
														lowerCAmelCase__			  =      100002 * base_num
														if is_9_pandigital(A			):
																					return candidate

							for base_num in range(333					,       99					,       -1			):
														lowerCAmelCase__			  =      1002003 * base_num
														if is_9_pandigital(A			):
																					return candidate

							return None


if __name__ == "__main__":
		print(f"""{solution() = }""")