"""simple docstring"""






from __future__ import annotations

from collections.abc import Callable
from typing import Any, Generic, TypeVar

__lowerCAmelCase    :       Optional[int]					     =TypeVar("""T""")





class  _A						(       Generic[T]	):

      def __init__(						self		,       __lowerCAmelCase		,       __lowerCAmelCase						):







            """simple docstring"""



            lowercase														=	None

            lowercase														=	len(__lowerCAmelCase						)
            lowercase														=	[any_type for _ in range(self.N						)] + arr
            lowercase														=	fnc
            self.build()

      def 				A__       (						self						):







            """simple docstring"""



            for p in range(self.N - 1		,       0		,       -1						):
                  lowercase														=	self.fn(self.st[p * 2]		,       self.st[p * 2 + 1]						)

      def 				A__       (						self		,       __lowerCAmelCase		,       __lowerCAmelCase						):







            """simple docstring"""



            p += self.N
            lowercase														=	v
            while p > 1:
                  lowercase														=	p // 2
                  lowercase														=	self.fn(self.st[p * 2]		,       self.st[p * 2 + 1]						)







      def 				A__       (						self		,       __lowerCAmelCase		,       __lowerCAmelCase						):  # noqa: E741







            """simple docstring"""



            lowercase							,							lowercase														=	l + self.N, r + self.N

            lowercase														=	None
            while l <= r:
                  if l % 2 == 1:
                        lowercase														=	self.st[l] if res is None else self.fn(__lowerCAmelCase		,       self.st[l]						)
                  if r % 2 == 0:
                        lowercase														=	self.st[r] if res is None else self.fn(__lowerCAmelCase		,       self.st[r]						)
                  lowercase							,							lowercase														=	(l + 1) // 2, (r - 1) // 2
            return res


if __name__ == "__main__":
       from functools import reduce

       __lowerCAmelCase    :       List[str]					     =[1, 1_0, -2, 9, -3, 8, 4, -7, 5, 6, 1_1, -1_2]

       __lowerCAmelCase    :       Any					     ={
           0: 7,
           1: 2,
           2: 6,
           3: -1_4,
           4: 5,
           5: 4,
           6: 7,
           7: -1_0,
           8: 9,
           9: 1_0,
           1_0: 1_2,
           1_1: 1,
       }

       __lowerCAmelCase    :       Dict					     =SegmentTree(test_array, min)
       __lowerCAmelCase    :       Tuple					     =SegmentTree(test_array, max)
       __lowerCAmelCase    :       Union[str, Any]					     =SegmentTree(test_array, lambda a, b: a + b)


       def 			UpperCAmelCase__       (				) ->    None:
             '''simple docstring'''


             for i in range(len(lowerCAmelCase__		)		):
                   for j in range(lowerCAmelCase__					,		len(lowerCAmelCase__		)		):
                         lowercase														=	reduce(lowerCAmelCase__					,		test_array[i : j + 1]		)
                         lowercase														=	reduce(lowerCAmelCase__					,		test_array[i : j + 1]		)
                         lowercase														=	reduce(lambda lowerCAmelCase__					,		lowerCAmelCase__		: a + b					,		test_array[i : j + 1]		)
                         assert min_range == min_segment_tree.query(lowerCAmelCase__					,		lowerCAmelCase__		)
                         assert max_range == max_segment_tree.query(lowerCAmelCase__					,		lowerCAmelCase__		)
                         assert sum_range == sum_segment_tree.query(lowerCAmelCase__					,		lowerCAmelCase__		)

       test_all_segments()

       for index, value in test_updates.items():
              __lowerCAmelCase    :       str					     =value
              min_segment_tree.update(index, value)
              max_segment_tree.update(index, value)
              sum_segment_tree.update(index, value)
              test_all_segments()




"""simple docstring"""






from __future__ import annotations


def 			UpperCAmelCase__       (				lowerCAmelCase__     :list[int]		) ->    int:
      '''simple docstring'''


      if not nums:
            return 0
      lowercase														=	nums[0]
      lowercase														=	0
      for num in nums[1:]:
            lowercase							,							lowercase														=	(
                max_excluding + num,
                max(lowerCAmelCase__					,		lowerCAmelCase__		),
            )
      return max(lowerCAmelCase__					,		lowerCAmelCase__		)


if __name__ == "__main__":
       import doctest

       doctest.testmod()



