





import math




class 					UpperCamelCase_    :


							def __init__(							self      :str							,			__A      :List[str]						)				->				Dict:



									"""simple docstring"""



									SCREAMING_SNAKE_CASE__								= len(__A						)
									SCREAMING_SNAKE_CASE__								= [0] * (
									    4 * self.N
									)  # approximate the overall size of segment tree with array N
									self.build(1							,			0							,			self.N - 1						)


							def        _snake_case					(							self      :List[str]							,			__A      :Tuple						)				->				Any:



									"""simple docstring"""



									return idx * 2


							def        _snake_case					(							self      :str							,			__A      :Tuple						)				->				List[str]:



									"""simple docstring"""



									return idx * 2 + 1


							def        _snake_case					(							self      :int							,			__A      :List[str]							,			__A      :List[Any]							,			__A      :str						)				->				Union[str, Any]:  # noqa: E741



									"""simple docstring"""



									if l == r:
											SCREAMING_SNAKE_CASE__								= A[l]
									else:
											SCREAMING_SNAKE_CASE__								= (l + r) // 2
											self.build(self.left(__A						)							,			__A							,			__A						)
											self.build(self.right(__A						)							,			mid + 1							,			__A						)
											SCREAMING_SNAKE_CASE__								= max(self.st[self.left(__A						)]							,			self.st[self.right(__A						)]						)


							def        _snake_case					(							self      :str							,			__A      :Dict							,			__A      :Optional[Any]							,			__A      :Tuple						)				->				int:



									"""simple docstring"""



									return self.update_recursive(1							,			0							,			self.N - 1							,			a - 1							,			b - 1							,			__A						)


							def        _snake_case					(							self      :str							,			__A      :Dict							,			__A      :Union[str, Any]							,			__A      :Tuple							,			__A      :List[Any]							,			__A      :Dict							,			__A      :Dict						)				->				str:  # noqa: E741



									"""simple docstring"""



									if r < a or l > b:
											return True
									if l == r:
											SCREAMING_SNAKE_CASE__								= val
											return True
									SCREAMING_SNAKE_CASE__								= (l + r) // 2
									self.update_recursive(self.left(__A						)							,			__A							,			__A							,			__A							,			__A							,			__A						)
									self.update_recursive(self.right(__A						)							,			mid + 1							,			__A							,			__A							,			__A							,			__A						)
									SCREAMING_SNAKE_CASE__								= max(self.st[self.left(__A						)]							,			self.st[self.right(__A						)]						)
									return True


							def        _snake_case					(							self      :Optional[int]							,			__A      :Tuple							,			__A      :str						)				->				Tuple:



									"""simple docstring"""



									return self.query_recursive(1							,			0							,			self.N - 1							,			a - 1							,			b - 1						)


							def        _snake_case					(							self      :List[Any]							,			__A      :List[str]							,			__A      :Union[str, Any]							,			__A      :str							,			__A      :Dict							,			__A      :int						)				->				Optional[Any]:  # noqa: E741



									"""simple docstring"""



									if r < a or l > b:
											return -math.inf
									if l >= a and r <= b:
											return self.st[idx]
									SCREAMING_SNAKE_CASE__								= (l + r) // 2
									SCREAMING_SNAKE_CASE__								= self.query_recursive(self.left(__A						)							,			__A							,			__A							,			__A							,			__A						)
									SCREAMING_SNAKE_CASE__								= self.query_recursive(self.right(__A						)							,			mid + 1							,			__A							,			__A							,			__A						)
									return max(__A							,			__A						)


							def        _snake_case					(							self      :Dict						)				->				Dict:



									"""simple docstring"""



									SCREAMING_SNAKE_CASE__								= []
									for i in range(1							,			N + 1						):
											show_list += [self.query(__A							,			__A						)]
									print(__A						)


if __name__ == "__main__":
	_lowerCamelCase							=     [1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
	_lowerCamelCase							=     15
	_lowerCamelCase							=     SegmentTree(A)
	print(segt.query(4, 6))
	print(segt.query(7, 11))
	print(segt.query(7, 12))
	segt.update(1, 3, 111)
	print(segt.query(1, 15))
	segt.update(7, 8, 235)
	segt.show_data()






from typing import Callable






def 			SCREAMING_SNAKE_CASE__							(    UpperCamelCase__:							Callable      ):

		def wrapper(UpperCamelCase__:							List[Any]      ):
				SCREAMING_SNAKE_CASE__								= function_with_docstring.__doc__
				return target_function

		return wrapper