


from collections.abc import Sequence
from queue import Queue







class 				snake_case__:







						'''simple docstring'''




						def __init__(				self   ,						__lowercase   ,						__lowercase   ,						__lowercase   ,						__lowercase=None   ,						__lowercase=None							)					->    List[Any]:
										lowerCAmelCase_ :      str    				=				start
										lowerCAmelCase_ :      str    				=				end
										lowerCAmelCase_ :      Union[str, Any]    				=				val
										lowerCAmelCase_ :      Tuple    				=				(start + end) // 2
										lowerCAmelCase_ :      List[Any]    				=				left
										lowerCAmelCase_ :      Union[str, Any]    				=				right




						def __repr__(				self							)					->    Tuple:
										return f"""SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})"""







class 				snake_case__:







						'''simple docstring'''




						def __init__(				self   ,						__lowercase   ,						__lowercase							)					->    int:
										lowerCAmelCase_ :      int    				=				collection
										lowerCAmelCase_ :      List[Any]    				=				function
										if self.collection:
														lowerCAmelCase_ :      Union[str, Any]    				=				self._build_tree(0   ,						len(__lowercase							) - 1							)




						def 						lowercase_ (				self   ,						__lowercase   ,						__lowercase							)					->    Any:
										self._update_tree(self.root   ,						__lowercase   ,						__lowercase							)




						def 						lowercase_ (				self   ,						__lowercase   ,						__lowercase							)					->    Tuple:
										return self._query_range(self.root   ,						__lowercase   ,						__lowercase							)




						def 						lowercase_ (				self   ,						__lowercase   ,						__lowercase							)					->    Dict:
										if start == end:
														return SegmentTreeNode(__lowercase   ,						__lowercase   ,						self.collection[start]							)
										lowerCAmelCase_ :      Optional[Any]    				=				(start + end) // 2
										lowerCAmelCase_ :      Dict    				=				self._build_tree(__lowercase   ,						__lowercase							)
										lowerCAmelCase_ :      List[Any]    				=				self._build_tree(mid + 1   ,						__lowercase							)
										return SegmentTreeNode(__lowercase   ,						__lowercase   ,						self.fn(left.val   ,						right.val							)   ,						__lowercase   ,						__lowercase							)




						def 						lowercase_ (				self   ,						__lowercase   ,						__lowercase   ,						__lowercase							)					->    List[str]:
										if node.start == i and node.end == i:
														lowerCAmelCase_ :      List[Any]    				=				val
														return
										if i <= node.mid:
														self._update_tree(node.left   ,						__lowercase   ,						__lowercase							)
										else:
														self._update_tree(node.right   ,						__lowercase   ,						__lowercase							)
										lowerCAmelCase_ :      List[str]    				=				self.fn(node.left.val   ,						node.right.val							)




						def 						lowercase_ (				self   ,						__lowercase   ,						__lowercase   ,						__lowercase							)					->    int:
										if node.start == i and node.end == j:
														return node.val

										if i <= node.mid:
														if j <= node.mid:
																		# range in left child tree
																		return self._query_range(node.left   ,						__lowercase   ,						__lowercase							)
														else:
																		# range in left child tree and right child tree
																		return self.fn(
																		    self._query_range(node.left   ,						__lowercase   ,						node.mid							)   ,						self._query_range(node.right   ,						node.mid + 1   ,						__lowercase							)   ,						)
										else:
														# range in right child tree
														return self._query_range(node.right   ,						__lowercase   ,						__lowercase							)




						def 						lowercase_ (				self							)					->    Any:
										if self.root is not None:
														lowerCAmelCase_ :      List[str]    				=				Queue()
														queue.put(self.root							)
														while not queue.empty():
																		lowerCAmelCase_ :      List[str]    				=				queue.get()
																		yield node

																		if node.left is not None:
																						queue.put(node.left							)

																		if node.right is not None:
																						queue.put(node.right							)


if __name__ == "__main__":
						import operator

						for fn in [operator.add, max, min]:
												print("""*""" * 50)
												_UpperCAmelCase			:  Any     =SegmentTree([2, 1, 5, 3, 4], fn)
												for node in arr.traverse():
																		print(node)
												print()

												arr.update(1, 5)
												for node in arr.traverse():
																		print(node)
												print()

												print(arr.query_range(3, 4))  # 7
												print(arr.query_range(2, 2))  # 5
												print(arr.query_range(1, 3))  # 13
												print()



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