


'''simple docstring'''






import random





def      UpperCAmelCase      (		lowerCamelCase_  :Any				,      lowerCamelCase_  :List[Any]				,      lowerCamelCase_  :Dict ):







		'''simple docstring'''
		snake_case_		:							int			       =						a[left_index]
		snake_case_		:							Optional[Any]			       =						left_index + 1
		for j in range(left_index + 1				,      lowerCamelCase_ ):
				if a[j] < pivot:
						snake_case_       ,      snake_case_		:							int			       =						a[i], a[j]
						i += 1
		snake_case_       ,      snake_case_		:							Optional[int]			       =						a[i - 1], a[left_index]
		return i - 1





def      UpperCAmelCase      (		lowerCamelCase_  :List[Any]				,      lowerCamelCase_  :Union[str, Any]				,      lowerCamelCase_  :List[Any] ):







		'''simple docstring'''
		if left < right:
				snake_case_		:							List[Any]			       =						random.randint(lowerCamelCase_				,      right - 1 )
				snake_case_       ,      snake_case_		:							int			       =						(
				    a[left],
				    a[pivot],
				)  # switches the pivot with the left most bound
				snake_case_		:							List[str]			       =						partition(lowerCamelCase_				,      lowerCamelCase_				,      lowerCamelCase_ )
				quick_sort_random(
				    lowerCamelCase_				,      lowerCamelCase_				,      lowerCamelCase_ )  # recursive quicksort to the left of the pivot point
				quick_sort_random(
				    lowerCamelCase_				,      pivot_index + 1				,      lowerCamelCase_ )  # recursive quicksort to the right of the pivot point





def      UpperCAmelCase      (		):







		'''simple docstring'''
		snake_case_		:							Tuple			       =						input("""Enter numbers separated by a comma:\n""" ).strip()
		snake_case_		:							List[str]			       =						[int(lowerCamelCase_ ) for item in user_input.split(""",""" )]

		quick_sort_random(lowerCamelCase_				,      0				,      len(lowerCamelCase_ ) )

		print(lowerCamelCase_ )


if __name__ == "__main__":
							main()



'''simple docstring'''






import math





def      UpperCAmelCase      (		lowerCamelCase_  :list				,      lowerCamelCase_  :int ):







		'''simple docstring'''
		snake_case_		:							Union[str, Any]			       =						len(lowerCamelCase_ )
		snake_case_		:							List[Any]			       =						int(math.floor(math.sqrt(lowerCamelCase_ ) ) )
		snake_case_		:							str			       =						0
		while arr[min(lowerCamelCase_				,      lowerCamelCase_ ) - 1] < x:
				snake_case_		:							Any			       =						step
				step += int(math.floor(math.sqrt(lowerCamelCase_ ) ) )
				if prev >= n:
						return -1

		while arr[prev] < x:
				snake_case_		:							Optional[Any]			       =						prev + 1
				if prev == min(lowerCamelCase_				,      lowerCamelCase_ ):
						return -1
		if arr[prev] == x:
				return prev
		return -1


if __name__ == "__main__":
							__A	:	Any     =     input('Enter numbers separated by a comma:\n').strip()
							__A	:	Union[str, Any]     =     [int(item) for item in user_input.split(',')]
							__A	:	Optional[int]     =     int(input('Enter the number to be searched:\n'))
							__A	:	int     =     jump_search(arr, x)
							if res == -1:
														print('Number not found!')
							else:
														print(F'Number {x} is at index {res}')