

'''simple docstring'''
def  _lowerCAmelCase      (		_UpperCamelCase		:  list							,				_UpperCamelCase		:  int							,				_UpperCamelCase		:  int       )   ->    None:
     """simple docstring"""




     if right <= left:
          return
     _SCREAMING_SNAKE_CASE												=_SCREAMING_SNAKE_CASE												=left
     _SCREAMING_SNAKE_CASE												=right
     _SCREAMING_SNAKE_CASE												=sorting[left]
     while i <= b:
          if sorting[i] < pivot:
               _SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE												=sorting[i], sorting[a]
               a += 1
               i += 1
          elif sorting[i] > pivot:
               _SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE												=sorting[i], sorting[b]
               b -= 1
          else:
               i += 1
     quick_sort_apartition(_UpperCamelCase							,				_UpperCamelCase							,				a - 1       )
     quick_sort_apartition(_UpperCamelCase							,				b + 1							,				_UpperCamelCase       )


def  _lowerCAmelCase      (		_UpperCamelCase		:  list							,				_UpperCamelCase		:  int							,				_UpperCamelCase		:  int       )   ->    None:
     """simple docstring"""




     if left < right:
          _SCREAMING_SNAKE_CASE												=lomuto_partition(_UpperCamelCase							,				_UpperCamelCase							,				_UpperCamelCase       )
          quick_sort_lomuto_partition(_UpperCamelCase							,				_UpperCamelCase							,				pivot_index - 1       )
          quick_sort_lomuto_partition(_UpperCamelCase							,				pivot_index + 1							,				_UpperCamelCase       )


def  _lowerCAmelCase      (		_UpperCamelCase		:  list							,				_UpperCamelCase		:  int							,				_UpperCamelCase		:  int       )   ->    int:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE												=sorting[right]
     _SCREAMING_SNAKE_CASE												=left
     for i in range(_UpperCamelCase							,				_UpperCamelCase       ):
          if sorting[i] < pivot:
               _SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE												=sorting[i], sorting[store_index]
               store_index += 1
     _SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE												=sorting[store_index], sorting[right]
     return store_index


def  _lowerCAmelCase      (		_UpperCamelCase		:  list       )   ->    list:
     """simple docstring"""




     if len(_UpperCamelCase       ) <= 1:
          return sorting
     return (
         three_way_radix_quicksort([i for i in sorting if i < sorting[0]]       )
         + [i for i in sorting if i == sorting[0]]
         + three_way_radix_quicksort([i for i in sorting if i > sorting[0]]       )
     )


if __name__ == "__main__":
     import doctest

     doctest.testmod(verbose=True)

     lowerCamelCase				:   Tuple      				=  input("Enter numbers separated by a comma:\n").strip()
     lowerCamelCase				:   str      				=  [int(item) for item in user_input.split(",")]
     quick_sort_apartition(unsorted, 0, len(unsorted) - 1)
     print(unsorted)



'''simple docstring'''
def  _lowerCAmelCase      (		_UpperCamelCase		:  Optional[int]							,				_UpperCamelCase		:  Optional[Any]       )   ->    Tuple:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE												=len(_UpperCamelCase       )
     # Create a stack and push index of fist element to it
     _SCREAMING_SNAKE_CASE												=[]
     st.append(0       )

     # Span value of first element is always 1
     _SCREAMING_SNAKE_CASE												=1

     # Calculate span values for rest of the elements
     for i in range(1							,				_UpperCamelCase       ):
          # Pop elements from stack while stack is not
          # empty and top of stack is smaller than price[i]
          while len(_UpperCamelCase       ) > 0 and price[st[0]] <= price[i]:
               st.pop()

          # If stack becomes empty, then price[i] is greater
          # than all elements on left of it, i.e. price[0],
          # price[1], ..price[i-1]. Else the price[i]  is
          # greater than elements after top of stack
          _SCREAMING_SNAKE_CASE												=i + 1 if len(_UpperCamelCase       ) <= 0 else (i - st[0])

          # Push this element to stack
          st.append(_UpperCamelCase       )


def  _lowerCAmelCase      (		_UpperCamelCase		:  Any							,				_UpperCamelCase		:  str       )   ->    Any:
     """simple docstring"""




     for i in range(0							,				_UpperCamelCase       ):
          print(arr[i]							,				end=' '       )


# Driver program to test above function
lowerCamelCase				:   str      				=  [1_0, 4, 5, 9_0, 1_2_0, 8_0]
lowerCamelCase				:   str      				=  [0 for i in range(len(price) + 1)]

# Fill the span values in array S[]
calculation_span(price, S)







print_array(S, len(price))
