


from __future__ import annotations

import math






class     UpperCAmelCase__       :



    """simple docstring"""






    def __init__(			self					,   A_    )  ->       None:
         __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 _a					(			self					,   A_    )  ->       int:
         return idx * 2






    def _a					(			self					,   A_    )  ->       int:
         return idx * 2 + 1






    def _a					(			self					,   A_					,   A_					,   A_					,   A_    )  ->       None:
         if left_element == right_element:
              __UpperCamelCase    							=a[left_element - 1]
         else:
              __UpperCamelCase    							=(left_element + right_element) // 2
              self.build(self.left(A_    )					,   A_					,   A_					,   A_    )
              self.build(self.right(A_    )					,   mid + 1					,   A_					,   A_    )
              __UpperCamelCase    							=max(
                  self.segment_tree[self.left(A_    )]					,   self.segment_tree[self.right(A_    )]    )






    def _a					(			self					,   A_					,   A_					,   A_					,   A_					,   A_					,   A_    )  ->       bool:
         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(A_    )					,   A_					,   A_					,   A_					,   A_					,   A_    )
         self.update(self.right(A_    )					,   mid + 1					,   A_					,   A_					,   A_					,   A_    )
         __UpperCamelCase    							=max(
             self.segment_tree[self.left(A_    )]					,   self.segment_tree[self.right(A_    )]    )
         return True






    def _a					(			self					,   A_					,   A_					,   A_					,   A_					,   A_    )  ->       int | float:
         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(A_    )					,   A_					,   A_					,   A_					,   A_    )
         __UpperCamelCase    							=self.query(self.right(A_    )					,   mid + 1					,   A_					,   A_					,   A_    )
         return max(A_					,   A_    )






    def __str__(			self    )  ->       str:
         return str([self.query(1					,   1					,   self.size					,   A_					,   A_    ) for i in range(1					,   self.size + 1    )]    )


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







import logging
import os
from logging import (
    CRITICAL,  # NOQA
    DEBUG,  # NOQA
    ERROR,  # NOQA
    FATAL,  # NOQA
    INFO,  # NOQA
    NOTSET,  # NOQA
    WARN,  # NOQA
    WARNING,  # NOQA
)
from typing import Optional

from tqdm import auto as tqdm_lib


lowercase__       ={
    'debug': logging.DEBUG,
    'info': logging.INFO,
    'warning': logging.WARNING,
    'error': logging.ERROR,
    'critical': logging.CRITICAL,
}

lowercase__       =logging.WARNING




def    __UpperCamelCase     (				):
 __a :  Optional[Any]						=  os.getenv('''DATASETS_VERBOSITY'''  ,   lowerCAmelCase__  )
 if env_level_str:
  if env_level_str in log_levels:
   return log_levels[env_level_str]
  else:
   logging.getLogger().warning(
       f"Unknown option DATASETS_VERBOSITY={env_level_str}, "
       f"has to be one of: { ', '.join(log_levels.keys()  ) }"  )
 return _default_log_level




def    __UpperCamelCase     (				):
 return __name__.split('''.'''  )[0]




def    __UpperCamelCase     (				):
 return logging.getLogger(_get_library_name()  )




def    __UpperCamelCase     (				):
 # Apply our default configuration to the library root logger.
 __a :  str						=  _get_library_root_logger()
 library_root_logger.setLevel(_get_default_logging_level()  )




def    __UpperCamelCase     (				):
 __a :  Any						=  _get_library_root_logger()
 library_root_logger.setLevel(logging.NOTSET  )




def    __UpperCamelCase     (				lowerCAmelCase__							:				Optional[str] = None  ):
 if name is None:
  __a :  Union[str, Any]						=  _get_library_name()
 return logging.getLogger(lowerCAmelCase__  )




def    __UpperCamelCase     (				):
 return _get_library_root_logger().getEffectiveLevel()




def    __UpperCamelCase     (				lowerCAmelCase__							:				int  ):
 _get_library_root_logger().setLevel(lowerCAmelCase__  )




def    __UpperCamelCase     (				):
 return set_verbosity(lowerCAmelCase__  )




def    __UpperCamelCase     (				):
 return set_verbosity(lowerCAmelCase__  )




def    __UpperCamelCase     (				):
 return set_verbosity(lowerCAmelCase__  )




def    __UpperCamelCase     (				):
 return set_verbosity(lowerCAmelCase__  )




def    __UpperCamelCase     (				):
 __a :  Union[str, Any]						=  False




def    __UpperCamelCase     (				):
 __a :  Tuple						=  True


# Configure the library root logger at the module level (singleton-like)
_configure_library_root_logger()



class 		UpperCamelCase__  :
   def __init__(self :					str					,				*snake_case_ :					str					,				**snake_case_ :					Union[str, Any]   ):  # pylint: disable=unused-argument
    __a :  Optional[Any]						=  args[0] if args else None
   def __iter__(self :					List[str]   ):
    return iter(self._iterator   )
   def __getattr__(self :					str					,				snake_case_ :					Optional[Any]   ):

    def empty_fn(*snake_case_ :					int					,				**snake_case_ :					int   ):  # pylint: disable=unused-argument
     return

    return empty_fn
   def __enter__(self :					Union[str, Any]   ):
    return self







   def __exit__(self :					str					,				snake_case_ :					List[str]					,				snake_case_ :					int					,				snake_case_ :					Optional[Any]   ):
    return





lowercase__       =True



class 		UpperCamelCase__  :
   def __call__(self :					Tuple					,				*snake_case_ :					str					,				snake_case_ :					str=False					,				**snake_case_ :					Dict   ):
    if _tqdm_active and not disable:
     return tqdm_lib.tqdm(*snake_case_					,				**snake_case_   )
    else:
     return EmptyTqdm(*snake_case_					,				**snake_case_   )
   def       lowerCAmelCase			(self :					Optional[Any]					,				*snake_case_ :					Union[str, Any]					,				**snake_case_ :					Optional[Any]   ):
    __a :  List[Any]						=  None
    if _tqdm_active:
     return tqdm_lib.tqdm.set_lock(*snake_case_					,				**snake_case_   )







   def       lowerCAmelCase			(self :					str   ):
    if _tqdm_active:
     return tqdm_lib.tqdm.get_lock()





lowercase__       =_tqdm_cls()




def    __UpperCamelCase     (				):
 global _tqdm_active
 return bool(_tqdm_active  )




def    __UpperCamelCase     (				):
 global _tqdm_active
 __a :  Dict						=  True




def    __UpperCamelCase     (				):
 global _tqdm_active
 __a :  Union[str, Any]						=  False
