






"""simple docstring"""




import functools
from math import sqrt
from time import time






def 						_SCREAMING_SNAKE_CASE							( UpperCamelCase     :	int		,				*UpperCamelCase     :	List[str]		,				**UpperCamelCase     :	Optional[int]    ):
  A__											=							time()
  A__											=							func(*UpperCamelCase		,				**UpperCamelCase    )
  A__											=							time()
  if int(end - start    ) > 0:
    print(F"""{func.__name__} runtime: {(end - start):0.4f} s"""    )
  else:
    print(F"""{func.__name__} runtime: {(end - start) * 1000:0.4f} ms"""    )
  return output






def 						_SCREAMING_SNAKE_CASE							( UpperCamelCase     :	int    ):
  if n < 0:
    raise Exception("""n is negative"""    )
  if n == 0:
    return [0]
  A__											=							[0, 1]
  for _ in range(n - 1    ):
    fib.append(fib[-1] + fib[-2]    )
  return fib






def 						_SCREAMING_SNAKE_CASE							( UpperCamelCase     :	int    ):

  def fib_recursive_term(UpperCamelCase     :	int    ) -> int:
    if i < 0:
      raise Exception("""n is negative"""    )
    if i < 2:
      return i
    return fib_recursive_term(i - 1    ) + fib_recursive_term(i - 2    )

  if n < 0:
    raise Exception("""n is negative"""    )
  return [fib_recursive_term(UpperCamelCase    ) for i in range(n + 1    )]






def 						_SCREAMING_SNAKE_CASE							( UpperCamelCase     :	int    ):

  @functools.cache
  def fib_recursive_term(UpperCamelCase     :	int    ) -> int:
    if i < 0:
      raise Exception("""n is negative"""    )
    if i < 2:
      return i
    return fib_recursive_term(i - 1    ) + fib_recursive_term(i - 2    )

  if n < 0:
    raise Exception("""n is negative"""    )
  return [fib_recursive_term(UpperCamelCase    ) for i in range(n + 1    )]






def 						_SCREAMING_SNAKE_CASE							( UpperCamelCase     :	int    ):
  if n < 0:
    raise Exception("""n is negative"""    )
  # Cache must be outside recursuive function
  # other it will reset every time it calls itself.
  A__											=							{0: 0, 1: 1, 2: 1}  # Prefilled cache

  def rec_fn_memoized(UpperCamelCase     :	int    ) -> int:
    if num in cache:
      return cache[num]

    A__											=							rec_fn_memoized(num - 1    ) + rec_fn_memoized(num - 2    )
    A__											=							value
    return value

  return [rec_fn_memoized(UpperCamelCase    ) for i in range(n + 1    )]






def 						_SCREAMING_SNAKE_CASE							( UpperCamelCase     :	int    ):
  if n < 0:
    raise Exception("""n is negative"""    )
  if n >= 1475:
    raise Exception("""n is too large"""    )
  A__											=							sqrt(5    )
  A__											=							(1 + sqrt_a) / 2
  return [round(phi**i / sqrt_a    ) for i in range(n + 1    )]


if __name__ == "__main__":
      lowerCamelCase__			=   30
      time_func(fib_iterative, num)
      time_func(fib_recursive, num)  # Around 3s runtime
      time_func(fib_recursive_cached, num)  # Around 0ms runtime
      time_func(fib_memoization, num)
      time_func(fib_binet, num)












"""simple docstring"""




def 						_SCREAMING_SNAKE_CASE							( UpperCamelCase     :	Dict    ):
  A__											=							len(UpperCamelCase    )
  for _ in range(
      0		,				int(((no_of_elements - 1) / 2) + 1    )    ):  # we don't need to traverse to end of list as
    for j in range(0		,				no_of_elements - 1    ):
      if (
          lst[j + 1] < lst[j]
      ):  # applying bubble sort algorithm from left to right (or forwards)
        A__											=							lst[j + 1]
        A__											=							lst[j]
        A__											=							temp
      if (
          lst[no_of_elements - 1 - j] < lst[no_of_elements - 2 - j]
      ):  # applying bubble sort algorithm from right to left (or backwards)
        A__											=							lst[no_of_elements - 1 - j]
        A__											=							lst[no_of_elements - 2 - j]
        A__											=							temp
  return lst


if __name__ == "__main__":
      print("enter the list to be sorted")
      lowerCamelCase__			=   [int(x) for x in input().split()]  # inputing elements of the list in one line
      lowerCamelCase__			=   double_sort(lst)
      print("the sorted list is")
      print(sorted_lst)




