





"""simple docstring"""





def 		lowerCAmelCase_     (  lowercase_       :							list			,				lowercase_       :							int			,				lowercase_       :							int			,				lowercase_       :							int		):

 '''simple docstring'''






 __SCREAMING_SNAKE_CASE			:      Optional[Any] 							=	int((lower_bound + upper_bound) // 2		)
 if array[r] == value:
  return r
 if lower_bound >= upper_bound:
  return -1
 if array[r] < value:
  return binary_search(lowercase_			,				r + 1			,				lowercase_			,				lowercase_		)
 else:
  return binary_search(lowercase_			,				lowercase_			,				r - 1			,				lowercase_		)




def 		lowerCAmelCase_     (  lowercase_       :							int			,				lowercase_       :							list		):

 '''simple docstring'''






 __SCREAMING_SNAKE_CASE			:      Optional[Any] 							=	0
 if matrix[index][0] == value:
  return [index, 0]
 while index < len(lowercase_		) and matrix[index][0] < value:
  __SCREAMING_SNAKE_CASE			:      Tuple 							=	binary_search(matrix[index]			,				0			,				len(matrix[index]		) - 1			,				lowercase_		)
  if r != -1:
   return [index, r]
  index += 1
 return [-1, -1]


if __name__ == "__main__":
    import doctest

    doctest.testmod()








"""simple docstring"""





import math





class       snake_case		:

      def __init__(      self       :Optional[Any]						,							_lowerCamelCase       :Dict						):
       __SCREAMING_SNAKE_CASE			:      str 							=	len(_lowerCamelCase						)
       __SCREAMING_SNAKE_CASE			:      Optional[int] 							=	[0] * (
           4 * self.N
       )  # approximate the overall size of segment tree with array N
       self.build(1						,							0						,							self.N - 1						)

      def 						SCREAMING_SNAKE_CASE_      (      self       :Union[str, Any]						,							_lowerCamelCase       :List[str]						):
       return idx * 2

      def 						SCREAMING_SNAKE_CASE_      (      self       :Tuple						,							_lowerCamelCase       :Optional[Any]						):
       return idx * 2 + 1

      def 						SCREAMING_SNAKE_CASE_      (      self       :int						,							_lowerCamelCase       :Optional[Any]						,							_lowerCamelCase       :Union[str, Any]						,							_lowerCamelCase       :str						):  # noqa: E741
       if l == r:
        __SCREAMING_SNAKE_CASE			:      Union[str, Any] 							=	A[l]
       else:
        __SCREAMING_SNAKE_CASE			:      Dict 							=	(l + r) // 2
        self.build(self.left(_lowerCamelCase						)						,							_lowerCamelCase						,							_lowerCamelCase						)
        self.build(self.right(_lowerCamelCase						)						,							mid + 1						,							_lowerCamelCase						)
        __SCREAMING_SNAKE_CASE			:      List[Any] 							=	max(self.st[self.left(_lowerCamelCase						)]						,							self.st[self.right(_lowerCamelCase						)]						)

      def 						SCREAMING_SNAKE_CASE_      (      self       :Tuple						,							_lowerCamelCase       :Optional[Any]						,							_lowerCamelCase       :Optional[Any]						,							_lowerCamelCase       :Union[str, Any]						):
       return self.update_recursive(1						,							0						,							self.N - 1						,							a - 1						,							b - 1						,							_lowerCamelCase						)

      def 						SCREAMING_SNAKE_CASE_      (      self       :Optional[int]						,							_lowerCamelCase       :Optional[Any]						,							_lowerCamelCase       :Any						,							_lowerCamelCase       :Union[str, Any]						,							_lowerCamelCase       :Optional[Any]						,							_lowerCamelCase       :str						,							_lowerCamelCase       :Optional[Any]						):  # noqa: E741
       if r < a or l > b:
        return True
       if l == r:
        __SCREAMING_SNAKE_CASE			:      Union[str, Any] 							=	val
        return True
       __SCREAMING_SNAKE_CASE			:      List[Any] 							=	(l + r) // 2
       self.update_recursive(self.left(_lowerCamelCase						)						,							_lowerCamelCase						,							_lowerCamelCase						,							_lowerCamelCase						,							_lowerCamelCase						,							_lowerCamelCase						)
       self.update_recursive(self.right(_lowerCamelCase						)						,							mid + 1						,							_lowerCamelCase						,							_lowerCamelCase						,							_lowerCamelCase						,							_lowerCamelCase						)
       __SCREAMING_SNAKE_CASE			:      Union[str, Any] 							=	max(self.st[self.left(_lowerCamelCase						)]						,							self.st[self.right(_lowerCamelCase						)]						)
       return True

      def 						SCREAMING_SNAKE_CASE_      (      self       :Tuple						,							_lowerCamelCase       :str						,							_lowerCamelCase       :Any						):
       return self.query_recursive(1						,							0						,							self.N - 1						,							a - 1						,							b - 1						)

      def 						SCREAMING_SNAKE_CASE_      (      self       :str						,							_lowerCamelCase       :Dict						,							_lowerCamelCase       :str						,							_lowerCamelCase       :Union[str, Any]						,							_lowerCamelCase       :Optional[Any]						,							_lowerCamelCase       :Any						):  # noqa: E741
       if r < a or l > b:
        return -math.inf
       if l >= a and r <= b:
        return self.st[idx]
       __SCREAMING_SNAKE_CASE			:      List[str] 							=	(l + r) // 2
       __SCREAMING_SNAKE_CASE			:      Any 							=	self.query_recursive(self.left(_lowerCamelCase						)						,							_lowerCamelCase						,							_lowerCamelCase						,							_lowerCamelCase						,							_lowerCamelCase						)
       __SCREAMING_SNAKE_CASE			:      Optional[int] 							=	self.query_recursive(self.right(_lowerCamelCase						)						,							mid + 1						,							_lowerCamelCase						,							_lowerCamelCase						,							_lowerCamelCase						)
       return max(_lowerCamelCase						,							_lowerCamelCase						)



      def 						SCREAMING_SNAKE_CASE_      (      self       :Dict						):
       __SCREAMING_SNAKE_CASE			:      str 							=	[]
       for i in range(1						,							N + 1						):
        show_list += [self.query(_lowerCamelCase						,							_lowerCamelCase						)]
       print(_lowerCamelCase						)


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, 1_11)
    print(segt.query(1, 15))
    segt.update(7, 8, 2_35)
    segt.show_data()

