





"""simple docstring"""
from __future__ import annotations

_snake_case					:		Any							=			[2, 1, 4, 5, 6, 0, 8, 9, 1, 2, 0, 6, 4, 2, 0, 6, 5, 3, 2, 7]






class  _UpperCAmelCase       :


					def __init__( self      :int					,	__UpperCamelCase      :int		):
												A		=  -1
												A		=  -1
												A		=  [-1] * length
												A		=  None
												A		=  None


					def __repr__( self      :int		):
												return f"Node(min_value={self.minn} max_value={self.maxx})"







def  A__    (      UpperCamelCase	):
							A		=  Node(len(UpperCamelCase	)	)
							A,     A		=  min(UpperCamelCase	), max(UpperCamelCase	)
							# Leaf node case where the node contains only one unique value
							if root.minn == root.maxx:
														return root
							A		=  (root.minn + root.maxx) // 2

							A		=  []
							A		=  []

							for index, num in enumerate(UpperCamelCase	):
														if num <= pivot:
																					left_arr.append(UpperCamelCase	)
														else:
																					right_arr.append(UpperCamelCase	)
														A		=  len(UpperCamelCase	)
							A		=  build_tree(UpperCamelCase	)
							A		=  build_tree(UpperCamelCase	)
							return root






def  A__    (      UpperCamelCase ,  UpperCamelCase ,  UpperCamelCase	):
							if index < 0 or node is None:
														return 0
							# Leaf node cases
							if node.minn == node.maxx:
														return index + 1 if node.minn == num else 0
							A		=  (node.minn + node.maxx) // 2
							if num <= pivot:
														# go the left subtree and map index to the left subtree
														return rank_till_index(node.left ,  UpperCamelCase ,  node.map_left[index] - 1	)
							else:
														# go to the right subtree and map index to the right subtree
														return rank_till_index(node.right ,  UpperCamelCase ,  index - node.map_left[index]	)






def  A__    (      UpperCamelCase ,  UpperCamelCase ,  UpperCamelCase ,  UpperCamelCase	):
							if start > end:
														return 0
							A		=  rank_till_index(UpperCamelCase ,  UpperCamelCase ,  UpperCamelCase	)
							A		=  rank_till_index(UpperCamelCase ,  UpperCamelCase ,  start - 1	)
							return rank_till_end - rank_before_start






def  A__    (      UpperCamelCase ,  UpperCamelCase ,  UpperCamelCase ,  UpperCamelCase	):
							if index > (end - start) or start > end or node is None:
														return -1
							# Leaf node case
							if node.minn == node.maxx:
														return node.minn
							# Number of elements in the left subtree in interval [start, end]
							A		=  node.map_left[end] - (
							    node.map_left[start - 1] if start else 0
							)
							if num_elements_in_left_tree > index:
														return quantile(
														    node.left ,  UpperCamelCase ,  (node.map_left[start - 1] if start else 0) ,  node.map_left[end] - 1 ,  )
							else:
														return quantile(
														    node.right ,  index - num_elements_in_left_tree ,  start - (node.map_left[start - 1] if start else 0) ,  end - node.map_left[end] ,  )






def  A__    (      UpperCamelCase ,  UpperCamelCase ,  UpperCamelCase ,  UpperCamelCase ,  UpperCamelCase	):
							if (
							    start > end
							    or node is None
							    or start_num > end_num
							    or node.minn > end_num
							    or node.maxx < start_num
							):
														return 0
							if start_num <= node.minn and node.maxx <= end_num:
														return end - start + 1
							A		=  range_counting(
							    node.left ,  (node.map_left[start - 1] if start else 0) ,  node.map_left[end] - 1 ,  UpperCamelCase ,  UpperCamelCase ,  )
							A		=  range_counting(
							    node.right ,  start - (node.map_left[start - 1] if start else 0) ,  end - node.map_left[end] ,  UpperCamelCase ,  UpperCamelCase ,  )
							return left + right


if __name__ == "__main__":
					import doctest

					doctest.testmod()









"""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}""")


