





"""simple docstring"""
class  _UpperCAmelCase       :


					def __init__( self      :int		):
												A		=  [0]
												A		=  0


					def      lowerCamelCase	( self      :Optional[int]					,	__UpperCamelCase      :int		):
												A		=  self.__heap[i]
												while i // 2 > 0:
																			if self.__heap[i] > self.__heap[i // 2]:
																										A		=  self.__heap[i // 2]
																										A		=  temporary
																			i //= 2


					def      lowerCamelCase	( self      :Any					,	__UpperCamelCase      :int		):
												self.__heap.append(__UpperCamelCase		)
												self.__size += 1
												self.__swap_up(self.__size		)


					def      lowerCamelCase	( self      :Dict					,	__UpperCamelCase      :int		):
												while self.__size >= 2 * i:
																			if 2 * i + 1 > self.__size:
																										A		=  2 * i
																			else:
																										if self.__heap[2 * i] > self.__heap[2 * i + 1]:
																																	A		=  2 * i
																										else:
																																	A		=  2 * i + 1
																			A		=  self.__heap[i]
																			if self.__heap[i] < self.__heap[bigger_child]:
																										A		=  self.__heap[bigger_child]
																										A		=  temporary
																			A		=  bigger_child


					def      lowerCamelCase	( self      :Dict		):
												A		=  self.__heap[1]
												A		=  self.__heap[self.__size]
												self.__size -= 1
												self.__heap.pop()
												self.__swap_down(1		)
												return max_value


					@property
					def      lowerCamelCase	( self      :Tuple		):
												return self.__heap[1:]


					def __len__( self      :List[str]		):
												return self.__size


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		# create an instance of BinaryHeap
		_snake_case					:		Union[str, Any]							=			BinaryHeap()
		binary_heap.insert(6)
		binary_heap.insert(10)
		binary_heap.insert(15)
		binary_heap.insert(12)
		# pop root(max-values because it is max heap)
		print(binary_heap.pop())  # 15
		print(binary_heap.pop())  # 12
		# get the list and size after operations
		print(binary_heap.get_list)
		print(len(binary_heap))









"""simple docstring"""
def  A__    (      UpperCamelCase ,  UpperCamelCase	):
							for index, item in enumerate(UpperCamelCase	):
														if item == target:
																					return index
							return -1






def  A__    (      UpperCamelCase ,  UpperCamelCase ,  UpperCamelCase ,  UpperCamelCase	):
							if not (0 <= high < len(UpperCamelCase	) and 0 <= low < len(UpperCamelCase	)):
														raise Exception("Invalid upper or lower bound!"	)
							if high < low:
														return -1
							if sequence[low] == target:
														return low
							if sequence[high] == target:
														return high
							return rec_linear_search(UpperCamelCase ,  low + 1 ,  high - 1 ,  UpperCamelCase	)


if __name__ == "__main__":
		_snake_case					:		int							=			input('Enter numbers separated by comma:\n').strip()
		_snake_case					:		int							=			[int(item.strip()) for item in user_input.split(',')]

		_snake_case					:		Union[str, Any]							=			int(input('Enter a single number to be found in the list:\n').strip())
		_snake_case					:		List[Any]							=			linear_search(sequence, target)
		if result != -1:
				print(F"""linear_search({sequence}, {target}) = {result}""")
		else:
				print(F"""{target} was not found in {sequence}""")


