
import math




class 	UpperCAmelCase_      :


  '''simple docstring'''







  def __init__(			self      :			Optional[int]      ,							UpperCamelCase__      :			str   )      ->     List[str]:







    """simple docstring"""






    __magic_name__    					=	len(UpperCamelCase__   )
    __magic_name__    					=	[0] * (
        4 * self.N
    )  # approximate the overall size of segment tree with array N
    self.build(1      ,							0      ,							self.N - 1   )
  def 							_lowercase							(			self      :			List[Any]      ,							UpperCamelCase__      :			Optional[Any]   )      ->     Optional[int]:







    """simple docstring"""






    return idx * 2
  def 							_lowercase							(			self      :			str      ,							UpperCamelCase__      :			Tuple   )      ->     List[str]:







    """simple docstring"""






    return idx * 2 + 1
  def 							_lowercase							(			self      :			int      ,							UpperCamelCase__      :			int      ,							UpperCamelCase__      :			Tuple      ,							UpperCamelCase__      :			Dict   )      ->     str:  # noqa: E741







    """simple docstring"""






    if l == r:
      __magic_name__    					=	A[l]
    else:
      __magic_name__    					=	(l + r) // 2
      self.build(self.left(UpperCamelCase__   )      ,							UpperCamelCase__      ,							UpperCamelCase__   )
      self.build(self.right(UpperCamelCase__   )      ,							mid + 1      ,							UpperCamelCase__   )
      __magic_name__    					=	max(self.st[self.left(UpperCamelCase__   )]      ,							self.st[self.right(UpperCamelCase__   )]   )
  def 							_lowercase							(			self      :			int      ,							UpperCamelCase__      :			Tuple      ,							UpperCamelCase__      :			Any      ,							UpperCamelCase__      :			Any   )      ->     Any:







    """simple docstring"""






    return self.update_recursive(1      ,							0      ,							self.N - 1      ,							a - 1      ,							b - 1      ,							UpperCamelCase__   )
  def 							_lowercase							(			self      :			Any      ,							UpperCamelCase__      :			Dict      ,							UpperCamelCase__      :			Dict      ,							UpperCamelCase__      :			str      ,							UpperCamelCase__      :			Optional[int]      ,							UpperCamelCase__      :			str      ,							UpperCamelCase__      :			Optional[Any]   )      ->     str:  # noqa: E741







    """simple docstring"""






    if r < a or l > b:
      return True
    if l == r:
      __magic_name__    					=	val
      return True
    __magic_name__    					=	(l + r) // 2
    self.update_recursive(self.left(UpperCamelCase__   )      ,							UpperCamelCase__      ,							UpperCamelCase__      ,							UpperCamelCase__      ,							UpperCamelCase__      ,							UpperCamelCase__   )
    self.update_recursive(self.right(UpperCamelCase__   )      ,							mid + 1      ,							UpperCamelCase__      ,							UpperCamelCase__      ,							UpperCamelCase__      ,							UpperCamelCase__   )
    __magic_name__    					=	max(self.st[self.left(UpperCamelCase__   )]      ,							self.st[self.right(UpperCamelCase__   )]   )
    return True
  def 							_lowercase							(			self      :			List[str]      ,							UpperCamelCase__      :			List[str]      ,							UpperCamelCase__      :			Optional[int]   )      ->     Union[str, Any]:







    """simple docstring"""






    return self.query_recursive(1      ,							0      ,							self.N - 1      ,							a - 1      ,							b - 1   )
  def 							_lowercase							(			self      :			Union[str, Any]      ,							UpperCamelCase__      :			str      ,							UpperCamelCase__      :			str      ,							UpperCamelCase__      :			Tuple      ,							UpperCamelCase__      :			Optional[Any]      ,							UpperCamelCase__      :			Union[str, Any]   )      ->     Any:  # noqa: E741







    """simple docstring"""






    if r < a or l > b:
      return -math.inf
    if l >= a and r <= b:
      return self.st[idx]
    __magic_name__    					=	(l + r) // 2
    __magic_name__    					=	self.query_recursive(self.left(UpperCamelCase__   )      ,							UpperCamelCase__      ,							UpperCamelCase__      ,							UpperCamelCase__      ,							UpperCamelCase__   )
    __magic_name__    					=	self.query_recursive(self.right(UpperCamelCase__   )      ,							mid + 1      ,							UpperCamelCase__      ,							UpperCamelCase__      ,							UpperCamelCase__   )
    return max(UpperCamelCase__      ,							UpperCamelCase__   )





  def 							_lowercase							(			self      :			int   )      ->     int:







    """simple docstring"""






    __magic_name__    					=	[]
    for i in range(1      ,							N + 1   ):
      show_list += [self.query(UpperCamelCase__      ,							UpperCamelCase__   )]
    print(UpperCamelCase__   )


if __name__ == "__main__":
    __lowerCAmelCase      :					int   	=       [1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
    __lowerCAmelCase      :					Optional[Any]   	=       15
    __lowerCAmelCase      :					Tuple   	=       SegmentTree(A)
    print(segt.query(4, 6))
    print(segt.query(7, 11))
    print(segt.query(7, 12))
    segt.update(1, 3, 111)
    print(segt.query(1, 15))
    segt.update(7, 8, 235)
    segt.show_data()



import sys

sys.set_int_max_str_digits(0)  # type: ignore

def a__   (	A_ ):






  '''simple docstring'''





  __magic_name__    					=	[0] * 11
  __magic_name__    					=	[0] * 11

  # mark last 9 numbers
  for _ in range(9 ):
    __magic_name__    					=	1
    __magic_name__    					=	number // 10
  # flag
  __magic_name__    					=	True

  # check last 9 numbers for pandigitality

  for x in range(9 ):
    if not check_last[x + 1]:
      __magic_name__    					=	False
  if not f:
    return f

  # mark first 9 numbers
  __magic_name__    					=	int(str(A_ )[:9] )

  for _ in range(9 ):
    __magic_name__    					=	1
    __magic_name__    					=	number // 10

  # check first 9 numbers for pandigitality

  for x in range(9 ):
    if not check_front[x + 1]:
      __magic_name__    					=	False
  return f

def a__   (	A_ ):






  '''simple docstring'''





  __magic_name__    					=	[0] * 11

  # mark last 9 numbers
  for _ in range(9 ):
    __magic_name__    					=	1
    __magic_name__    					=	number // 10
  # flag
  __magic_name__    					=	True

  # check last 9 numbers for pandigitality

  for x in range(9 ):
    if not check_last[x + 1]:
      __magic_name__    					=	False
  return f

def a__   (	):






  '''simple docstring'''





  __magic_name__    					=	1
  __magic_name__    					=	1
  __magic_name__    					=	2
  # temporary Fibonacci numbers

  __magic_name__    					=	1
  __magic_name__    					=	1
  __magic_name__    					=	2
  # temporary Fibonacci numbers mod 1e9

  # mod m=1e9, done for fast optimisation
  __magic_name__    					=	[0] * 1000000
  __magic_name__    					=	1000000000

  for x in range(1000000 ):
    __magic_name__    					=	(aa + ba) % m
    __magic_name__    					=	ba % m
    __magic_name__    					=	ca % m
    if checka(A_ ):
      __magic_name__    					=	1

  for x in range(1000000 ):
    __magic_name__    					=	a + b
    __magic_name__    					=	b
    __magic_name__    					=	c
    # perform check only if in tocheck
    if tocheck[x + 3] and check(A_ ):
      return x + 3  # first 2 already done
  return -1


if __name__ == "__main__":
    print(F'''{solution() = }''')

