




"""simple docstring"""






# This code is adapted from OpenAI's release
# https://github.com/openai/human-eval/blob/master/human_eval/execution.py

import contextlib
import faulthandler
import io
import multiprocessing
import os
import platform
import signal
import tempfile







def      _snake_case			(				lowercase__							,    lowercase__							,    lowercase__							,    lowercase__		):
				_lowerCamelCase     :			Any    =    multiprocessing.Manager()
				_lowerCamelCase     :			str    =    manager.list()

				_lowerCamelCase     :			int    =    multiprocessing.Process(target=lowercase__							,    args=(check_program, result, timeout)		)
				p.start()
				p.join(timeout=timeout + 1		)
				if p.is_alive():
								p.kill()

				if not result:
								result.append('timed out'		)

				return {
				    "task_id": task_id,
				    "passed": result[0] == "passed",
				    "result": result[0],
				    "completion_id": completion_id,
				}







def      _snake_case			(				lowercase__							,    lowercase__							,    lowercase__		):
				with create_tempdir():
								# These system calls are needed when cleaning up tempdir.
								import os
								import shutil

								_lowerCamelCase     :			Optional[Any]    =    shutil.rmtree
								_lowerCamelCase     :			Dict    =    os.rmdir
								_lowerCamelCase     :			int    =    os.chdir

								# Disable functionalities that can make destructive changes to the test.
								reliability_guard()

								# Run program.
								try:
												_lowerCamelCase     :			Dict    =    {}
												with swallow_io():
																with time_limit(lowercase__		):
																				exec(lowercase__							,    lowercase__		)
												result.append('passed'		)
								except TimeoutException:
												result.append('timed out'		)
								except BaseException as e:
												result.append(f'''failed: {e}'''		)

								# Needed for cleaning up.
								_lowerCamelCase     :			int    =    rmtree
								_lowerCamelCase     :			Tuple    =    rmdir
								_lowerCamelCase     :			List[Any]    =    chdir







@contextlib.contextmanager
def      _snake_case			(				lowercase__		):
				def signal_handler(lowercase__							,    lowercase__		):
								raise TimeoutException('Timed out!'		)

				signal.setitimer(signal.ITIMER_REAL							,    lowercase__		)
				signal.signal(signal.SIGALRM							,    lowercase__		)
				try:
								yield
				finally:
								signal.setitimer(signal.ITIMER_REAL							,    0		)







@contextlib.contextmanager
def      _snake_case			(				):
				_lowerCamelCase     :			Tuple    =    WriteOnlyStringIO()
				with contextlib.redirect_stdout(lowercase__		):
								with contextlib.redirect_stderr(lowercase__		):
												with redirect_stdin(lowercase__		):
																yield







@contextlib.contextmanager
def      _snake_case			(				):
				with tempfile.TemporaryDirectory() as dirname:
								with chdir(lowercase__		):
												yield dirname






class lowerCAmelCase__	(     lowercase						):






			'''simple docstring'''



			pass






class lowerCAmelCase__	(     io.StringIO						):






			'''simple docstring'''



			def 					A_    (  self  ,      *lowercase  ,      **lowercase  ):
							raise OSError
			def 					A_    (  self  ,      *lowercase  ,      **lowercase  ):
							raise OSError
			def 					A_    (  self  ,      *lowercase  ,      **lowercase  ):
							raise OSError






			def 					A_    (  self  ,      *lowercase  ,      **lowercase  ):
							return False






class lowerCAmelCase__	(     contextlib._RedirectStream						):  # type: ignore






			'''simple docstring'''



			lowerCamelCase__      =			"""stdin"""







@contextlib.contextmanager
def      _snake_case			(				lowercase__		):
				if root == ".":
								yield
								return
				_lowerCamelCase     :			List[str]    =    os.getcwd()
				os.chdir(lowercase__		)
				try:
								yield
				except BaseException as exc:
								raise exc
				finally:
								os.chdir(lowercase__		)







def      _snake_case			(				lowercase__=None		):

				if maximum_memory_bytes is not None:
								import resource

								resource.setrlimit(resource.RLIMIT_AS							,    (maximum_memory_bytes, maximum_memory_bytes)		)
								resource.setrlimit(resource.RLIMIT_DATA							,    (maximum_memory_bytes, maximum_memory_bytes)		)
								if not platform.uname().system == "Darwin":
												resource.setrlimit(resource.RLIMIT_STACK							,    (maximum_memory_bytes, maximum_memory_bytes)		)

				faulthandler.disable()

				import builtins

				_lowerCamelCase     :			Dict    =    None
				_lowerCamelCase     :			Any    =    None

				import os

				_lowerCamelCase     :			Optional[Any]    =    '1'

				_lowerCamelCase     :			Union[str, Any]    =    None
				_lowerCamelCase     :			Dict    =    None
				_lowerCamelCase     :			str    =    None
				_lowerCamelCase     :			Optional[Any]    =    None
				_lowerCamelCase     :			Optional[Any]    =    None
				_lowerCamelCase     :			Union[str, Any]    =    None
				_lowerCamelCase     :			List[str]    =    None
				_lowerCamelCase     :			Any    =    None
				_lowerCamelCase     :			str    =    None
				_lowerCamelCase     :			int    =    None
				_lowerCamelCase     :			int    =    None
				_lowerCamelCase     :			Tuple    =    None
				_lowerCamelCase     :			Any    =    None
				_lowerCamelCase     :			List[Any]    =    None
				_lowerCamelCase     :			Any    =    None
				_lowerCamelCase     :			Any    =    None
				_lowerCamelCase     :			List[str]    =    None
				_lowerCamelCase     :			Optional[int]    =    None
				_lowerCamelCase     :			Any    =    None
				_lowerCamelCase     :			Any    =    None
				_lowerCamelCase     :			List[Any]    =    None
				_lowerCamelCase     :			List[str]    =    None
				_lowerCamelCase     :			Optional[Any]    =    None
				_lowerCamelCase     :			Union[str, Any]    =    None
				_lowerCamelCase     :			List[Any]    =    None
				_lowerCamelCase     :			Optional[int]    =    None
				_lowerCamelCase     :			str    =    None

				import shutil

				_lowerCamelCase     :			str    =    None
				_lowerCamelCase     :			int    =    None
				_lowerCamelCase     :			Any    =    None

				import subprocess

				_lowerCamelCase     :			List[Any]    =    None  # type: ignore

				_lowerCamelCase     :			Union[str, Any]    =    None

				import sys

				_lowerCamelCase     :			Optional[int]    =    None
				_lowerCamelCase     :			Dict    =    None
				_lowerCamelCase     :			str    =    None
				_lowerCamelCase     :			List[Any]    =    None
				_lowerCamelCase     :			int    =    None

"""simple docstring"""





from __future__ import annotations

__magic_name__       =			[-10, -5, 0, 5, 5.1, 11, 13, 21, 3, 4, -21, -10, -5, -1, 0]
__magic_name__       =			[-5, 0, 5, 5.1, 11, 13, 21, -1, 4, -1, -10, -5, -1, 0, -1]



def 						_lowerCAmelCase				(				UpperCamelCase_				):
		__SCREAMING_SNAKE_CASE            = []
		__SCREAMING_SNAKE_CASE            = len(UpperCamelCase_				)

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



def 						_lowerCAmelCase				(				UpperCamelCase_				):
		__SCREAMING_SNAKE_CASE            = []
		for i, outer in enumerate(UpperCamelCase_				):
				__SCREAMING_SNAKE_CASE            = -1
				for inner in arr[i + 1 :]:
						if outer < inner:
								__SCREAMING_SNAKE_CASE            = inner
								break
				result.append(UpperCamelCase_				)
		return result



def 						_lowerCAmelCase				(				UpperCamelCase_				):
		__SCREAMING_SNAKE_CASE            = len(UpperCamelCase_				)
		__SCREAMING_SNAKE_CASE            = []
		__SCREAMING_SNAKE_CASE            = [-1] * arr_size

		for index in reversed(range(UpperCamelCase_				)				):
				if stack:
						while stack[-1] <= arr[index]:
								stack.pop()
								if not stack:
										break
				if stack:
						__SCREAMING_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))

							__magic_name__       =			(
							    "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),
							)




