






import math
class    a   :



						"""simple docstring"""


						def __init__(				self :      List[str]		,				__lowercase :      int )							->				Optional[int]:
								__UpperCAmelCase							:     List[str]									=  len(__lowercase )
								__UpperCAmelCase							:     Union[str, Any]									=  [0] * (
								    4 * self.N
								)  # approximate the overall size of segment tree with array N
								self.build(1		,				0		,				self.N - 1 )
						def      UpperCAmelCase				(				self :      Dict		,				__lowercase :      Any )							->				List[str]:
								return idx * 2
						def      UpperCAmelCase				(				self :      int		,				__lowercase :      Optional[Any] )							->				Dict:
								return idx * 2 + 1
						def      UpperCAmelCase				(				self :      Optional[Any]		,				__lowercase :      Tuple		,				__lowercase :      Optional[Any]		,				__lowercase :      List[Any] )							->				str:  # noqa: E741
								if l == r:
										__UpperCAmelCase							:     Tuple									=  A[l]
								else:
										__UpperCAmelCase							:     Union[str, Any]									=  (l + r) // 2
										self.build(self.left(__lowercase )		,				__lowercase		,				__lowercase )
										self.build(self.right(__lowercase )		,				mid + 1		,				__lowercase )
										__UpperCAmelCase							:     Optional[Any]									=  max(self.st[self.left(__lowercase )]		,				self.st[self.right(__lowercase )] )
						def      UpperCAmelCase				(				self :      str		,				__lowercase :      Dict		,				__lowercase :      int		,				__lowercase :      Dict )							->				Union[str, Any]:
								return self.update_recursive(1		,				0		,				self.N - 1		,				a - 1		,				b - 1		,				__lowercase )
						def      UpperCAmelCase				(				self :      Tuple		,				__lowercase :      Dict		,				__lowercase :      str		,				__lowercase :      int		,				__lowercase :      Union[str, Any]		,				__lowercase :      List[Any]		,				__lowercase :      Dict )							->				Union[str, Any]:  # noqa: E741
								if r < a or l > b:
										return True
								if l == r:
										__UpperCAmelCase							:     List[Any]									=  val
										return True
								__UpperCAmelCase							:     Tuple									=  (l + r) // 2
								self.update_recursive(self.left(__lowercase )		,				__lowercase		,				__lowercase		,				__lowercase		,				__lowercase		,				__lowercase )
								self.update_recursive(self.right(__lowercase )		,				mid + 1		,				__lowercase		,				__lowercase		,				__lowercase		,				__lowercase )
								__UpperCAmelCase							:     Optional[int]									=  max(self.st[self.left(__lowercase )]		,				self.st[self.right(__lowercase )] )
								return True
						def      UpperCAmelCase				(				self :      str		,				__lowercase :      Optional[Any]		,				__lowercase :      Any )							->				int:
								return self.query_recursive(1		,				0		,				self.N - 1		,				a - 1		,				b - 1 )
						def      UpperCAmelCase				(				self :      Optional[Any]		,				__lowercase :      Any		,				__lowercase :      Optional[int]		,				__lowercase :      Any		,				__lowercase :      Optional[int]		,				__lowercase :      List[str] )							->				Optional[Any]:  # noqa: E741
								if r < a or l > b:
										return -math.inf
								if l >= a and r <= b:
										return self.st[idx]
								__UpperCAmelCase							:     List[Any]									=  (l + r) // 2
								__UpperCAmelCase							:     List[Any]									=  self.query_recursive(self.left(__lowercase )		,				__lowercase		,				__lowercase		,				__lowercase		,				__lowercase )
								__UpperCAmelCase							:     Any									=  self.query_recursive(self.right(__lowercase )		,				mid + 1		,				__lowercase		,				__lowercase		,				__lowercase )
								return max(__lowercase		,				__lowercase )




						def      UpperCAmelCase				(				self :      Tuple )							->				Optional[int]:
								__UpperCAmelCase							:     Dict									=  []
								for i in range(1		,				N + 1 ):
										show_list += [self.query(__lowercase		,				__lowercase )]
								print(__lowercase )


if __name__ == "__main__":
							a		:	str      					=			[1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
							a		:	int      					=			15
							a		:	Any      					=			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()










def     lowerCamelCase__				(   __lowerCamelCase      :					list		):
  if len(__lowerCamelCase		) <= 1:
    return data
  else:
    return [
        *quick_sort([e for e in data[1:] if e <= data[0]]		),
        data[0],
        *quick_sort([e for e in data[1:] if e > data[0]]		),
    ]


if __name__ == "__main__":
       import doctest

       doctest.testmod()


