





import importlib.metadata
import sys

from transformers.testing_utils import TestCasePlus
from transformers.utils.versions import require_version, require_version_core


UpperCAmelCase_       : List[str]							=    importlib.metadata.version("""numpy""")
UpperCAmelCase_       : Tuple							=    """.""".join([str(x) for x in sys.version_info[:3]])





class   lowercase__     (				__A	):







  def 						UpperCAmelCase__		(						self    ):
       # lt + different version strings
       require_version_core("""numpy<1000.4.5"""    )
       require_version_core("""numpy<1000.4"""    )
       require_version_core("""numpy<1000"""    )

       # le
       require_version_core("""numpy<=1000.4.5"""    )
       require_version_core(F'numpy<={numpy_ver}'    )

       # eq
       require_version_core(F'numpy=={numpy_ver}'    )

       # ne
       require_version_core("""numpy!=1000.4.5"""    )

       # ge
       require_version_core("""numpy>=1.0"""    )
       require_version_core("""numpy>=1.0.0"""    )
       require_version_core(F'numpy>={numpy_ver}'    )

       # gt
       require_version_core("""numpy>1.0.0"""    )

       # mix
       require_version_core("""numpy>1.0.0,<1000"""    )

       # requirement w/o version
       require_version_core("""numpy"""    )

       # unmet requirements due to version conflict
       for req in ["numpy==1.0.0", "numpy>=1000.0.0", F'numpy<{numpy_ver}']:
            try:
                 require_version_core(_lowercase    )
            except ImportError as e:
                 self.assertIn(F'{req} is required'     ,    str(_lowercase    )    )
                 self.assertIn("""but found"""     ,    str(_lowercase    )    )

        # unmet requirements due to missing module
       for req in ["numpipypie>1", "numpipypie2"]:
            try:
                 require_version_core(_lowercase    )
            except importlib.metadata.PackageNotFoundError as e:
                 self.assertIn(F'The \'{req}\' distribution was not found and is required by this application'     ,    str(_lowercase    )    )
                 self.assertIn("""Try: pip install transformers -U"""     ,    str(_lowercase    )    )

        # bogus requirements formats:
        # 1. whole thing
       for req in ["numpy??1.0.0", "numpy1.0.0"]:
            try:
                 require_version_core(_lowercase    )
            except ValueError as e:
                 self.assertIn("""requirement needs to be in the pip package format"""     ,    str(_lowercase    )    )
        # 2. only operators
       for req in ["numpy=1.0.0", "numpy == 1.00", "numpy<>1.0.0", "numpy><1.00", "numpy>>1.0.0"]:
            try:
                 require_version_core(_lowercase    )
            except ValueError as e:
                 self.assertIn("""need one of """     ,    str(_lowercase    )    )







  def 						UpperCAmelCase__		(						self    ):
       # matching requirement
       require_version("""python>=3.6.0"""    )

       # not matching requirements
       for req in ["python>9.9.9", "python<3.0.0"]:
            try:
                 require_version_core(_lowercase    )
            except ImportError as e:
                 self.assertIn(F'{req} is required'     ,    str(_lowercase    )    )
                 self.assertIn(F'but found python=={python_ver}'     ,    str(_lowercase    )    )







import math





class   lowercase__     :







  def __init__(						self     ,    _lowercase    ):
       lowerCAmelCase_       :							Optional[Any]			 =		len(_lowercase    )
       lowerCAmelCase_       :							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     ,    _lowercase    ):
       return idx * 2







  def 						UpperCAmelCase__		(						self     ,    _lowercase    ):
       return idx * 2 + 1







  def 						UpperCAmelCase__		(						self     ,    _lowercase     ,    _lowercase     ,    _lowercase    ):  # noqa: E741
       if l == r:
            lowerCAmelCase_       :							Dict			 =		A[l]
       else:
            lowerCAmelCase_       :							List[str]			 =		(l + r) // 2
            self.build(self.left(_lowercase    )     ,    _lowercase     ,    _lowercase    )
            self.build(self.right(_lowercase    )     ,    mid + 1     ,    _lowercase    )
            lowerCAmelCase_       :							Dict			 =		max(self.st[self.left(_lowercase    )]     ,    self.st[self.right(_lowercase    )]    )







  def 						UpperCAmelCase__		(						self     ,    _lowercase     ,    _lowercase     ,    _lowercase    ):
       return self.update_recursive(1     ,    0     ,    self.N - 1     ,    a - 1     ,    b - 1     ,    _lowercase    )







  def 						UpperCAmelCase__		(						self     ,    _lowercase     ,    _lowercase     ,    _lowercase     ,    _lowercase     ,    _lowercase     ,    _lowercase    ):  # noqa: E741
       if r < a or l > b:
            return True
       if l == r:
            lowerCAmelCase_       :							List[str]			 =		val
            return True
       lowerCAmelCase_       :							List[str]			 =		(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    )
       lowerCAmelCase_       :							List[Any]			 =		max(self.st[self.left(_lowercase    )]     ,    self.st[self.right(_lowercase    )]    )
       return True







  def 						UpperCAmelCase__		(						self     ,    _lowercase     ,    _lowercase    ):
       return self.query_recursive(1     ,    0     ,    self.N - 1     ,    a - 1     ,    b - 1    )







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







  def 						UpperCAmelCase__		(						self    ):
       lowerCAmelCase_       :							List[Any]			 =		[]
       for i in range(1     ,    N + 1    ):
            show_list += [self.query(_lowercase     ,    _lowercase    )]
       print(_lowercase    )


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