
from __future__ import annotations

import math




class        SCREAMING_SNAKE_CASE__					:





	'''simple docstring'''



	def __init__(  self     :   Dict      ,  lowercase     :   int     ):


				'''simple docstring'''


				_snake_case          =      size
				# approximate the overall size of segment tree with given value
				_snake_case          =      [0 for i in range(0      ,  4 * size     )]
				# create array to store lazy update
				_snake_case          =      [0 for i in range(0      ,  4 * size     )]
				_snake_case          =      [0 for i in range(0      ,  4 * size     )]  # flag for lazy update



	def 			A							(  self     :   Union[str, Any]      ,  lowercase     :   int     ):


				'''simple docstring'''


				return idx * 2



	def 			A							(  self     :   Optional[int]      ,  lowercase     :   int     ):


				'''simple docstring'''


				return idx * 2 + 1



	def 			A							(  self     :   str      ,  lowercase     :   int      ,  lowercase     :   int      ,  lowercase     :   int      ,  lowercase     :   list[int]     ):


				'''simple docstring'''


				if left_element == right_element:
							_snake_case          =      a[left_element - 1]
				else:
							_snake_case          =      (left_element + right_element) // 2
							self.build(self.left(lowercase     )      ,  lowercase      ,  lowercase      ,  lowercase     )
							self.build(self.right(lowercase     )      ,  mid + 1      ,  lowercase      ,  lowercase     )
							_snake_case          =      max(
							    self.segment_tree[self.left(lowercase     )]      ,  self.segment_tree[self.right(lowercase     )]     )



	def 			A							(  self     :   str      ,  lowercase     :   int      ,  lowercase     :   int      ,  lowercase     :   int      ,  lowercase     :   int      ,  lowercase     :   int      ,  lowercase     :   int     ):


				'''simple docstring'''


				if self.flag[idx] is True:
							_snake_case          =      self.lazy[idx]
							_snake_case          =      False
							if left_element != right_element:
										_snake_case          =      self.lazy[idx]
										_snake_case          =      self.lazy[idx]
										_snake_case          =      True
										_snake_case          =      True

				if right_element < a or left_element > b:
							return True
				if left_element >= a and right_element <= b:
							_snake_case          =      val
							if left_element != right_element:
										_snake_case          =      val
										_snake_case          =      val
										_snake_case          =      True
										_snake_case          =      True
							return True
				_snake_case          =      (left_element + right_element) // 2
				self.update(self.left(lowercase     )      ,  lowercase      ,  lowercase      ,  lowercase      ,  lowercase      ,  lowercase     )
				self.update(self.right(lowercase     )      ,  mid + 1      ,  lowercase      ,  lowercase      ,  lowercase      ,  lowercase     )
				_snake_case          =      max(
				    self.segment_tree[self.left(lowercase     )]      ,  self.segment_tree[self.right(lowercase     )]     )
				return True



	def 			A							(  self     :   str      ,  lowercase     :   int      ,  lowercase     :   int      ,  lowercase     :   int      ,  lowercase     :   int      ,  lowercase     :   int     ):


				'''simple docstring'''


				if self.flag[idx] is True:
							_snake_case          =      self.lazy[idx]
							_snake_case          =      False
							if left_element != right_element:
										_snake_case          =      self.lazy[idx]
										_snake_case          =      self.lazy[idx]
										_snake_case          =      True
										_snake_case          =      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]
				_snake_case          =      (left_element + right_element) // 2
				_snake_case          =      self.query(self.left(lowercase     )      ,  lowercase      ,  lowercase      ,  lowercase      ,  lowercase     )
				_snake_case          =      self.query(self.right(lowercase     )      ,  mid + 1      ,  lowercase      ,  lowercase      ,  lowercase     )
				return max(lowercase      ,  lowercase     )





	def __str__(  self     :   List[str]     ):


				'''simple docstring'''


				return str([self.query(1      ,  1      ,  self.size      ,  lowercase      ,  lowercase     ) for i in range(1      ,  self.size + 1     )]     )


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

from __future__ import annotations

_lowerCamelCase	:    Optional[Any]          =      [-10, -5, 0, 5, 5.1, 11, 13, 21, 3, 4, -21, -10, -5, -1, 0]
_lowerCamelCase	:    Optional[int]          =      [-5, 0, 5, 5.1, 11, 13, 21, -1, 4, -1, -10, -5, -1, 0, -1]






def 	a_		(	__lowercase       :     list[float]			)			->  list[float]:
			_snake_case          =      []
			_snake_case          =      len(__lowercase			)

			for i in range(__lowercase			):
						_snake_case          =      -1
						for j in range(i + 1	, __lowercase			):
									if arr[i] < arr[j]:
												_snake_case          =      arr[j]
												break
						result.append(__lowercase			)
			return result






def 	a_		(	__lowercase       :     list[float]			)			->  list[float]:
			_snake_case          =      []
			for i, outer in enumerate(__lowercase			):
						_snake_case          =      -1
						for inner in arr[i + 1 :]:
									if outer < inner:
												_snake_case          =      inner
												break
						result.append(__lowercase			)
			return result






def 	a_		(	__lowercase       :     list[float]			)			->  list[float]:
			_snake_case          =      len(__lowercase			)
			_snake_case          =      []
			_snake_case          =      [-1] * arr_size

			for index in reversed(range(__lowercase			)			):
						if stack:
									while stack[-1] <= arr[index]:
												stack.pop()
												if not stack:
															break
						if stack:
									_snake_case          =      stack[-1]
						stack.append(arr[index]			)
			return result


if __name__ == "__main__":
			from doctest import testmod
			from timeit import timeit

			testmod()
			print(next_greatest_element_slow(arr))
			print(next_greatest_element_fast(arr))
			print(next_greatest_element(arr))

			_lowerCamelCase	:    Union[str, Any]          =      (
			    '''from __main__ import arr, next_greatest_element_slow, '''
			    '''next_greatest_element_fast, next_greatest_element'''
			)
			print(
			    '''next_greatest_element_slow():''',
			    timeit('''next_greatest_element_slow(arr)''', setup=setup),
			)
			print(
			    '''next_greatest_element_fast():''',
			    timeit('''next_greatest_element_fast(arr)''', setup=setup),
			)
			print(
			    '''     next_greatest_element():''',
			    timeit('''next_greatest_element(arr)''', setup=setup),
			)