






from __future__ import annotations

from random import choice





def 		__UpperCAmelCase     (	a_):
							return choice(a_)





def 		__UpperCAmelCase     (	a_				,	a_):
							snake_case_           =				random_pivot(a_)

							# partition based on pivot
							# linear time
							snake_case_           =				[e for e in lst if e < pivot]
							snake_case_           =				[e for e in lst if e > pivot]

							# if we get lucky, pivot might be the element we want.
							# we can easily see this:
							# small (elements smaller than k)
							# + pivot (kth element)
							# + big (elements larger than k)
							if len(a_) == k - 1:
														return pivot
							# pivot is in elements bigger than k
							elif len(a_) < k - 1:
														return kth_number(a_				,	k - len(a_) - 1)
							# pivot is in elements smaller than k
							else:
														return kth_number(a_				,	a_)


if __name__ == "__main__":
	import doctest

	doctest.testmod()













class 					UpperCamelCase_ :



	'''simple docstring'''




	def __init__(			self			,     a   )			->       Tuple:
								snake_case_           =				n
								snake_case_           =				[None] * self.n
								snake_case_           =				0  # index of the first element
								snake_case_           =				0
								snake_case_           =				0




	def __len__(			self   )			->       int:
								return self.size




	def 				_UpperCamelCase     (			self   )			->       bool:
								return self.size == 0




	def 				_UpperCamelCase     (			self   )			->       List[Any]:
								return False if self.is_empty() else self.array[self.front]




	def 				_UpperCamelCase     (			self			,     a   )			->       Dict:
								if self.size >= self.n:
															raise Exception('QUEUE IS FULL'   )

								snake_case_           =				data
								snake_case_           =				(self.rear + 1) % self.n
								self.size += 1
								return self






	def 				_UpperCamelCase     (			self   )			->       List[Any]:
								if self.size == 0:
															raise Exception('UNDERFLOW'   )

								snake_case_           =				self.array[self.front]
								snake_case_           =				None
								snake_case_           =				(self.front + 1) % self.n
								self.size -= 1
								return temp





