
"""simple docstring"""





def 						_lowerCAmelCase				(				UpperCamelCase_  ,				UpperCamelCase_  ,				UpperCamelCase_				):

		def count_of_possible_combinations(UpperCamelCase_				) -> int:
				if target < 0:
						return 0
				if target == 0:
						return 1
				return sum(count_of_possible_combinations(target - item				) for item in array				)

		return count_of_possible_combinations(UpperCamelCase_				)



def 						_lowerCAmelCase				(				UpperCamelCase_  ,				UpperCamelCase_  ,				UpperCamelCase_				):

		def count_of_possible_combinations_with_dp_array(
		    UpperCamelCase_  ,				UpperCamelCase_				) -> int:
				if target < 0:
						return 0
				if target == 0:
						return 1
				if dp_array[target] != -1:
						return dp_array[target]
				__SCREAMING_SNAKE_CASE            = sum(
				    count_of_possible_combinations_with_dp_array(target - item  ,				UpperCamelCase_				)
				    for item in array				)
				__SCREAMING_SNAKE_CASE            = answer
				return answer

		__SCREAMING_SNAKE_CASE            = [-1] * (target + 1)
		return count_of_possible_combinations_with_dp_array(UpperCamelCase_  ,				UpperCamelCase_				)



def 						_lowerCAmelCase				(				UpperCamelCase_  ,				UpperCamelCase_  ,				UpperCamelCase_				):
		__SCREAMING_SNAKE_CASE            = [0] * (target + 1)
		__SCREAMING_SNAKE_CASE            = 1

		for i in range(1  ,				target + 1				):
				for j in range(UpperCamelCase_				):
						if i - array[j] >= 0:
								dp_array[i] += dp_array[i - array[j]]

		return dp_array[target]


if __name__ == "__main__":
							import doctest

							doctest.testmod()
							__magic_name__       =			3
							__magic_name__       =			5
							__magic_name__       =			[1, 2, 5]
							print(combination_sum_iv(n, array, target))






"""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),
							)




