




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







      def 						UpperCAmelCase_    (      self :Any   )  ->      str:
       UpperCAmelCase__							=    []
       for i in range(1			,   N + 1   ):
        show_list += [self.query(lowerCamelCase			,   lowerCamelCase   )]
       print(lowerCamelCase   )


if __name__ == "__main__":
  _lowerCAmelCase    : Any		= [1, 2, -4, 7, 3, -5, 6, 1_1, -2_0, 9, 1_4, 1_5, 5, 2, -8]
  _lowerCAmelCase    : Dict		= 1_5
  _lowerCAmelCase    : List[str]		= SegmentTree(A)
  print(segt.query(4, 6))
  print(segt.query(7, 1_1))
  print(segt.query(7, 1_2))
  segt.update(1, 3, 1_1_1)
  print(segt.query(1, 1_5))
  segt.update(7, 8, 2_3_5)
  segt.show_data()











def     lowerCAmelCase		(		_lowerCAmelCase				: Tuple    ,				_lowerCAmelCase				: Tuple						):




 """simple docstring"""







 sequence.append(_lowerCAmelCase						)

 UpperCAmelCase__							=    0
 while sequence[index] != target:
  index += 1

 sequence.pop()

 if index == len(_lowerCAmelCase						):
  return None

 return index


if __name__ == "__main__":
  _lowerCAmelCase    : List[Any]		= input("Enter numbers separated by comma:\n").strip()
  _lowerCAmelCase    : Dict		= [int(item) for item in user_input.split(",")]

  _lowerCAmelCase    : Optional[Any]		= input("Enter a single number to be found in the list:\n")
  _lowerCAmelCase    : Tuple		= int(target_input)
  _lowerCAmelCase    : int		= sentinel_linear_search(sequence, target)
  if result is not None:
    print(F'''{target} found at positions: {result}''')
  else:
    print("Not found")





