



from __future__ import annotations

import math





class  __magic_name__   :






		def __init__(						self      :     Optional[int]				,		UpperCamelCase__      :     int      )				->					None:
								'''simple docstring'''







								UpperCAmelCase         =     size
								# approximate the overall size of segment tree with given value
								UpperCAmelCase         =     [0 for i in range(0				,		4 * size      )]
								# create array to store lazy update
								UpperCAmelCase         =     [0 for i in range(0				,		4 * size      )]
								UpperCAmelCase         =     [0 for i in range(0				,		4 * size      )]  # flag for lazy update






		def SCREAMING_SNAKE_CASE_			(						self      :     str				,		UpperCamelCase__      :     int      )				->					int:
								'''simple docstring'''







								return idx * 2






		def SCREAMING_SNAKE_CASE_			(						self      :     Tuple				,		UpperCamelCase__      :     int      )				->					int:
								'''simple docstring'''







								return idx * 2 + 1






		def SCREAMING_SNAKE_CASE_			(						self      :     str				,		UpperCamelCase__      :     int				,		UpperCamelCase__      :     int				,		UpperCamelCase__      :     int				,		UpperCamelCase__      :     list[int]      )				->					None:
								'''simple docstring'''







								if left_element == right_element:
														UpperCAmelCase         =     a[left_element - 1]
								else:
														UpperCAmelCase         =     (left_element + right_element) // 2
														self.build(self.left(UpperCamelCase__      )				,		UpperCamelCase__				,		UpperCamelCase__				,		UpperCamelCase__      )
														self.build(self.right(UpperCamelCase__      )				,		mid + 1				,		UpperCamelCase__				,		UpperCamelCase__      )
														UpperCAmelCase         =     max(
														    self.segment_tree[self.left(UpperCamelCase__      )]				,		self.segment_tree[self.right(UpperCamelCase__      )]      )






		def SCREAMING_SNAKE_CASE_			(						self      :     Dict				,		UpperCamelCase__      :     int				,		UpperCamelCase__      :     int				,		UpperCamelCase__      :     int				,		UpperCamelCase__      :     int				,		UpperCamelCase__      :     int				,		UpperCamelCase__      :     int      )				->					bool:
								'''simple docstring'''







								if self.flag[idx] is True:
														UpperCAmelCase         =     self.lazy[idx]
														UpperCAmelCase         =     False
														if left_element != right_element:
																				UpperCAmelCase         =     self.lazy[idx]
																				UpperCAmelCase         =     self.lazy[idx]
																				UpperCAmelCase         =     True
																				UpperCAmelCase         =     True

								if right_element < a or left_element > b:
														return True
								if left_element >= a and right_element <= b:
														UpperCAmelCase         =     val
														if left_element != right_element:
																				UpperCAmelCase         =     val
																				UpperCAmelCase         =     val
																				UpperCAmelCase         =     True
																				UpperCAmelCase         =     True
														return True
								UpperCAmelCase         =     (left_element + right_element) // 2
								self.update(self.left(UpperCamelCase__      )				,		UpperCamelCase__				,		UpperCamelCase__				,		UpperCamelCase__				,		UpperCamelCase__				,		UpperCamelCase__      )
								self.update(self.right(UpperCamelCase__      )				,		mid + 1				,		UpperCamelCase__				,		UpperCamelCase__				,		UpperCamelCase__				,		UpperCamelCase__      )
								UpperCAmelCase         =     max(
								    self.segment_tree[self.left(UpperCamelCase__      )]				,		self.segment_tree[self.right(UpperCamelCase__      )]      )
								return True






		def SCREAMING_SNAKE_CASE_			(						self      :     Dict				,		UpperCamelCase__      :     int				,		UpperCamelCase__      :     int				,		UpperCamelCase__      :     int				,		UpperCamelCase__      :     int				,		UpperCamelCase__      :     int      )				->					int | float:
								'''simple docstring'''







								if self.flag[idx] is True:
														UpperCAmelCase         =     self.lazy[idx]
														UpperCAmelCase         =     False
														if left_element != right_element:
																				UpperCAmelCase         =     self.lazy[idx]
																				UpperCAmelCase         =     self.lazy[idx]
																				UpperCAmelCase         =     True
																				UpperCAmelCase         =     True
								if right_element < a or left_element > b:
														return -math.inf
								if left_element >= a and right_element <= b:
														return self.segment_tree[idx]
								UpperCAmelCase         =     (left_element + right_element) // 2
								UpperCAmelCase         =     self.query(self.left(UpperCamelCase__      )				,		UpperCamelCase__				,		UpperCamelCase__				,		UpperCamelCase__				,		UpperCamelCase__      )
								UpperCAmelCase         =     self.query(self.right(UpperCamelCase__      )				,		mid + 1				,		UpperCamelCase__				,		UpperCamelCase__				,		UpperCamelCase__      )
								return max(UpperCamelCase__				,		UpperCamelCase__      )







		def __str__(						self      :     int      )				->					str:
								'''simple docstring'''







								return str([self.query(1				,		1				,		self.size				,		UpperCamelCase__				,		UpperCamelCase__      ) for i in range(1				,		self.size + 1      )]      )


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








from __future__ import annotations

def    lowerCamelCase_(lowerCamelCase_    ) ->       int:
						UpperCAmelCase         =     len(lowerCamelCase_    ) // 2

						# choose the middle 3 elements
						UpperCAmelCase         =     lst[m - 1 : m + 2]

						# if middle element is peak
						if three[1] > three[0] and three[1] > three[2]:
												return three[1]

						# if increasing, recurse on right
						elif three[0] < three[2]:
												if len(lst[:m]    ) == 2:
																		m -= 1
												return peak(lst[m:]    )

						# decreasing
						else:
												if len(lst[:m]    ) == 2:
																		m += 1
												return peak(lst[:m]    )


if __name__ == "__main__":
		import doctest

		doctest.testmod()



