


'''simple docstring'''






from __future__ import annotations

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


def       _snake_case     (  A )		->					list[float]:
							lowerCAmelCase__      =			[]
							lowerCAmelCase__      =			len(A )

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


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


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

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

		__UpperCAmelCase					       =							(
		    '''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),
		)



'''simple docstring'''






def       _snake_case     (  A				,					A )		->					bool:
							lowerCAmelCase__      =			len(A ) + 1
							lowerCAmelCase__      =			len(A ) + 1

							# dp is a 2d matrix where dp[i][j] denotes whether prefix string of
							# length i of input_string matches with prefix string of length j of
							# given pattern.
							# "dp" stands for dynamic programming.
							lowerCAmelCase__      =			[[0 for i in range(A )] for j in range(A )]

							# since string of zero length match pattern of zero length
							lowerCAmelCase__      =			1

							# since pattern of zero length will never match with string of non-zero length
							for i in range(1				,					A ):
														lowerCAmelCase__      =			0

							# since string of zero length will match with pattern where there
							# is at least one * alternatively
							for j in range(1				,					A ):
														lowerCAmelCase__      =			dp[0][j - 2] if pattern[j - 1] == '''*''' else 0

							# now using bottom-up approach to find for all remaining lengths
							for i in range(1				,					A ):
														for j in range(1				,					A ):
																					if input_string[i - 1] == pattern[j - 1] or pattern[j - 1] == ".":
																												lowerCAmelCase__      =			dp[i - 1][j - 1]

																					elif pattern[j - 1] == "*":
																												if dp[i][j - 2] == 1:
																																			lowerCAmelCase__      =			1
																												elif pattern[j - 2] in (input_string[i - 1], "."):
																																			lowerCAmelCase__      =			dp[i - 1][j]
																												else:
																																			lowerCAmelCase__      =			0
																					else:
																												lowerCAmelCase__      =			0

							return bool(dp[-1][-1] )


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		# inputing the strings
		# input_string = input("input a string :")
		# pattern = input("input a pattern :")

		__UpperCAmelCase					       =							'''aab'''
		__UpperCAmelCase					       =							'''c*a*b'''

		# using function to check whether given string matches the given pattern
		if match_pattern(input_string, pattern):
				print(f"""{input_string} matches the given pattern {pattern}""")
		else:
				print(f"""{input_string} does not match with the given pattern {pattern}""")