
'''simple docstring'''



from collections import deque
from math import floor
from random import random
from time import time




class   UpperCAmelCase_					:






						'''simple docstring'''






						def __init__( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			{}




						def  _lowercase     ( self   ,       _lowercase   ,       _lowercase   ,       _lowercase=1				):

												"""simple docstring"""



												if self.graph.get(_lowercase				):
																		if self.graph[u].count([w, v]				) == 0:
																								self.graph[u].append([w, v]				)
												else:
																		_lowerCAmelCase  						=			[[w, v]]
												if not self.graph.get(_lowercase				):
																		_lowerCAmelCase  						=			[]




						def  _lowercase     ( self				):

												"""simple docstring"""



												return list(self.graph				)




						def  _lowercase     ( self   ,       _lowercase   ,       _lowercase				):

												"""simple docstring"""



												if self.graph.get(_lowercase				):
																		for _ in self.graph[u]:
																								if _[1] == v:
																														self.graph[u].remove(_lowercase				)




						def  _lowercase     ( self   ,       _lowercase=-2   ,       _lowercase=-1				):

												"""simple docstring"""



												if s == d:
																		return []
												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			[]
												if s == -2:
																		_lowerCAmelCase  						=			list(self.graph				)[0]
												stack.append(_lowercase				)
												visited.append(_lowercase				)
												_lowerCAmelCase  						=			s

												while True:
																		# check if there is any non isolated nodes
																		if len(self.graph[s]				) != 0:
																								_lowerCAmelCase  						=			s
																								for node in self.graph[s]:
																														if visited.count(node[1]				) < 1:
																																				if node[1] == d:
																																										visited.append(_lowercase				)
																																										return visited
																																				else:
																																										stack.append(node[1]				)
																																										visited.append(node[1]				)
																																										_lowerCAmelCase  						=			node[1]
																																										break

            # check if all the children are visited
																		if s == ss:
																								stack.pop()
																								if len(_lowercase				) != 0:
																														_lowerCAmelCase  						=			stack[len(_lowercase				) - 1]
																		else:
																								_lowerCAmelCase  						=			ss

																		# check if se have reached the starting point
																		if len(_lowercase				) == 0:
																								return visited




						def  _lowercase     ( self   ,       _lowercase=-1				):

												"""simple docstring"""



												if c == -1:
																		_lowerCAmelCase  						=			floor(random() * 10_000				) + 10
												for i in range(_lowercase				):
																		# every vertex has max 100 edges
																		for _ in range(floor(random() * 102				) + 1				):
																								_lowerCAmelCase  						=			floor(random() * c				) + 1
																								if n != i:
																														self.add_pair(_lowercase   ,       _lowercase   ,       1				)




						def  _lowercase     ( self   ,       _lowercase=-2				):

												"""simple docstring"""



												_lowerCAmelCase  						=			deque()
												_lowerCAmelCase  						=			[]
												if s == -2:
																		_lowerCAmelCase  						=			list(self.graph				)[0]
												d.append(_lowercase				)
												visited.append(_lowercase				)
												while d:
																		_lowerCAmelCase  						=			d.popleft()
																		if len(self.graph[s]				) != 0:
																								for node in self.graph[s]:
																														if visited.count(node[1]				) < 1:
																																				d.append(node[1]				)
																																				visited.append(node[1]				)
												return visited




						def  _lowercase     ( self   ,       _lowercase				):

												"""simple docstring"""



												_lowerCAmelCase  						=			0
												for x in self.graph:
																		for y in self.graph[x]:
																								if y[1] == u:
																														count += 1
												return count




						def  _lowercase     ( self   ,       _lowercase				):

												"""simple docstring"""



												return len(self.graph[u]				)




						def  _lowercase     ( self   ,       _lowercase=-2				):

												"""simple docstring"""



												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			[]
												if s == -2:
																		_lowerCAmelCase  						=			list(self.graph				)[0]
												stack.append(_lowercase				)
												visited.append(_lowercase				)
												_lowerCAmelCase  						=			s
												_lowerCAmelCase  						=			[]

												while True:
																		# check if there is any non isolated nodes
																		if len(self.graph[s]				) != 0:
																								_lowerCAmelCase  						=			s
																								for node in self.graph[s]:
																														if visited.count(node[1]				) < 1:
																																				stack.append(node[1]				)
																																				visited.append(node[1]				)
																																				_lowerCAmelCase  						=			node[1]
																																				break

            # check if all the children are visited
																		if s == ss:
																								sorted_nodes.append(stack.pop()				)
																								if len(_lowercase				) != 0:
																														_lowerCAmelCase  						=			stack[len(_lowercase				) - 1]
																		else:
																								_lowerCAmelCase  						=			ss

																		# check if se have reached the starting point
																		if len(_lowercase				) == 0:
																								return sorted_nodes




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			list(self.graph				)[0]
												stack.append(_lowercase				)
												visited.append(_lowercase				)
												_lowerCAmelCase  						=			-2
												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			s
												_lowerCAmelCase  						=			False
												_lowerCAmelCase  						=			set()

												while True:
																		# check if there is any non isolated nodes
																		if len(self.graph[s]				) != 0:
																								_lowerCAmelCase  						=			s
																								for node in self.graph[s]:
																														if (
																														    visited.count(node[1]				) > 0
																														    and node[1] != parent
																														    and indirect_parents.count(node[1]				) > 0
																														    and not on_the_way_back
																														):
																																				_lowerCAmelCase  						=			len(_lowercase				) - 1
																																				while len_stack >= 0:
																																										if stack[len_stack] == node[1]:
																																																anticipating_nodes.add(node[1]				)
																																																break
																																										else:
																																																anticipating_nodes.add(stack[len_stack]				)
																																																len_stack -= 1
																														if visited.count(node[1]				) < 1:
																																				stack.append(node[1]				)
																																				visited.append(node[1]				)
																																				_lowerCAmelCase  						=			node[1]
																																				break

            # check if all the children are visited
																		if s == ss:
																								stack.pop()
																								_lowerCAmelCase  						=			True
																								if len(_lowercase				) != 0:
																														_lowerCAmelCase  						=			stack[len(_lowercase				) - 1]
																		else:
																								_lowerCAmelCase  						=			False
																								indirect_parents.append(_lowercase				)
																								_lowerCAmelCase  						=			s
																								_lowerCAmelCase  						=			ss

																		# check if se have reached the starting point
																		if len(_lowercase				) == 0:
																								return list(_lowercase				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			list(self.graph				)[0]
												stack.append(_lowercase				)
												visited.append(_lowercase				)
												_lowerCAmelCase  						=			-2
												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			s
												_lowerCAmelCase  						=			False
												_lowerCAmelCase  						=			set()

												while True:
																		# check if there is any non isolated nodes
																		if len(self.graph[s]				) != 0:
																								_lowerCAmelCase  						=			s
																								for node in self.graph[s]:
																														if (
																														    visited.count(node[1]				) > 0
																														    and node[1] != parent
																														    and indirect_parents.count(node[1]				) > 0
																														    and not on_the_way_back
																														):
																																				_lowerCAmelCase  						=			len(_lowercase				) - 1
																																				while len_stack_minus_one >= 0:
																																										if stack[len_stack_minus_one] == node[1]:
																																																anticipating_nodes.add(node[1]				)
																																																break
																																										else:
																																																return True
																														if visited.count(node[1]				) < 1:
																																				stack.append(node[1]				)
																																				visited.append(node[1]				)
																																				_lowerCAmelCase  						=			node[1]
																																				break

            # check if all the children are visited
																		if s == ss:
																								stack.pop()
																								_lowerCAmelCase  						=			True
																								if len(_lowercase				) != 0:
																														_lowerCAmelCase  						=			stack[len(_lowercase				) - 1]
																		else:
																								_lowerCAmelCase  						=			False
																								indirect_parents.append(_lowercase				)
																								_lowerCAmelCase  						=			s
																								_lowerCAmelCase  						=			ss

																		# check if se have reached the starting point
																		if len(_lowercase				) == 0:
																								return False




						def  _lowercase     ( self   ,       _lowercase=-2   ,       _lowercase=-1				):

												"""simple docstring"""



												_lowerCAmelCase  						=			time()
												self.dfs(_lowercase   ,       _lowercase				)
												_lowerCAmelCase  						=			time()
												return end - begin




						def  _lowercase     ( self   ,       _lowercase=-2				):

												"""simple docstring"""



												_lowerCAmelCase  						=			time()
												self.bfs(_lowercase				)
												_lowerCAmelCase  						=			time()
												return end - begin






class   UpperCAmelCase_					:






						'''simple docstring'''






						def __init__( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			{}




						def  _lowercase     ( self   ,       _lowercase   ,       _lowercase   ,       _lowercase=1				):

												"""simple docstring"""



												if self.graph.get(_lowercase				):
																		# if there already is a edge
																		if self.graph[u].count([w, v]				) == 0:
																								self.graph[u].append([w, v]				)
												else:
																		# if u does not exist
																		_lowerCAmelCase  						=			[[w, v]]
												# add the other way
												if self.graph.get(_lowercase				):
																		# if there already is a edge
																		if self.graph[v].count([w, u]				) == 0:
																								self.graph[v].append([w, u]				)
												else:
																		# if u does not exist
																		_lowerCAmelCase  						=			[[w, u]]




						def  _lowercase     ( self   ,       _lowercase   ,       _lowercase				):

												"""simple docstring"""



												if self.graph.get(_lowercase				):
																		for _ in self.graph[u]:
																								if _[1] == v:
																														self.graph[u].remove(_lowercase				)
        # the other way round
												if self.graph.get(_lowercase				):
																		for _ in self.graph[v]:
																								if _[1] == u:
																														self.graph[v].remove(_lowercase				)




						def  _lowercase     ( self   ,       _lowercase=-2   ,       _lowercase=-1				):

												"""simple docstring"""



												if s == d:
																		return []
												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			[]
												if s == -2:
																		_lowerCAmelCase  						=			list(self.graph				)[0]
												stack.append(_lowercase				)
												visited.append(_lowercase				)
												_lowerCAmelCase  						=			s

												while True:
																		# check if there is any non isolated nodes
																		if len(self.graph[s]				) != 0:
																								_lowerCAmelCase  						=			s
																								for node in self.graph[s]:
																														if visited.count(node[1]				) < 1:
																																				if node[1] == d:
																																										visited.append(_lowercase				)
																																										return visited
																																				else:
																																										stack.append(node[1]				)
																																										visited.append(node[1]				)
																																										_lowerCAmelCase  						=			node[1]
																																										break

            # check if all the children are visited
																		if s == ss:
																								stack.pop()
																								if len(_lowercase				) != 0:
																														_lowerCAmelCase  						=			stack[len(_lowercase				) - 1]
																		else:
																								_lowerCAmelCase  						=			ss

																		# check if se have reached the starting point
																		if len(_lowercase				) == 0:
																								return visited




						def  _lowercase     ( self   ,       _lowercase=-1				):

												"""simple docstring"""



												if c == -1:
																		_lowerCAmelCase  						=			floor(random() * 10_000				) + 10
												for i in range(_lowercase				):
																		# every vertex has max 100 edges
																		for _ in range(floor(random() * 102				) + 1				):
																								_lowerCAmelCase  						=			floor(random() * c				) + 1
																								if n != i:
																														self.add_pair(_lowercase   ,       _lowercase   ,       1				)




						def  _lowercase     ( self   ,       _lowercase=-2				):

												"""simple docstring"""



												_lowerCAmelCase  						=			deque()
												_lowerCAmelCase  						=			[]
												if s == -2:
																		_lowerCAmelCase  						=			list(self.graph				)[0]
												d.append(_lowercase				)
												visited.append(_lowercase				)
												while d:
																		_lowerCAmelCase  						=			d.popleft()
																		if len(self.graph[s]				) != 0:
																								for node in self.graph[s]:
																														if visited.count(node[1]				) < 1:
																																				d.append(node[1]				)
																																				visited.append(node[1]				)
												return visited




						def  _lowercase     ( self   ,       _lowercase				):

												"""simple docstring"""



												return len(self.graph[u]				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			list(self.graph				)[0]
												stack.append(_lowercase				)
												visited.append(_lowercase				)
												_lowerCAmelCase  						=			-2
												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			s
												_lowerCAmelCase  						=			False
												_lowerCAmelCase  						=			set()

												while True:
																		# check if there is any non isolated nodes
																		if len(self.graph[s]				) != 0:
																								_lowerCAmelCase  						=			s
																								for node in self.graph[s]:
																														if (
																														    visited.count(node[1]				) > 0
																														    and node[1] != parent
																														    and indirect_parents.count(node[1]				) > 0
																														    and not on_the_way_back
																														):
																																				_lowerCAmelCase  						=			len(_lowercase				) - 1
																																				while len_stack >= 0:
																																										if stack[len_stack] == node[1]:
																																																anticipating_nodes.add(node[1]				)
																																																break
																																										else:
																																																anticipating_nodes.add(stack[len_stack]				)
																																																len_stack -= 1
																														if visited.count(node[1]				) < 1:
																																				stack.append(node[1]				)
																																				visited.append(node[1]				)
																																				_lowerCAmelCase  						=			node[1]
																																				break

            # check if all the children are visited
																		if s == ss:
																								stack.pop()
																								_lowerCAmelCase  						=			True
																								if len(_lowercase				) != 0:
																														_lowerCAmelCase  						=			stack[len(_lowercase				) - 1]
																		else:
																								_lowerCAmelCase  						=			False
																								indirect_parents.append(_lowercase				)
																								_lowerCAmelCase  						=			s
																								_lowerCAmelCase  						=			ss

																		# check if se have reached the starting point
																		if len(_lowercase				) == 0:
																								return list(_lowercase				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			list(self.graph				)[0]
												stack.append(_lowercase				)
												visited.append(_lowercase				)
												_lowerCAmelCase  						=			-2
												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			s
												_lowerCAmelCase  						=			False
												_lowerCAmelCase  						=			set()

												while True:
																		# check if there is any non isolated nodes
																		if len(self.graph[s]				) != 0:
																								_lowerCAmelCase  						=			s
																								for node in self.graph[s]:
																														if (
																														    visited.count(node[1]				) > 0
																														    and node[1] != parent
																														    and indirect_parents.count(node[1]				) > 0
																														    and not on_the_way_back
																														):
																																				_lowerCAmelCase  						=			len(_lowercase				) - 1
																																				while len_stack_minus_one >= 0:
																																										if stack[len_stack_minus_one] == node[1]:
																																																anticipating_nodes.add(node[1]				)
																																																break
																																										else:
																																																return True
																														if visited.count(node[1]				) < 1:
																																				stack.append(node[1]				)
																																				visited.append(node[1]				)
																																				_lowerCAmelCase  						=			node[1]
																																				break

            # check if all the children are visited
																		if s == ss:
																								stack.pop()
																								_lowerCAmelCase  						=			True
																								if len(_lowercase				) != 0:
																														_lowerCAmelCase  						=			stack[len(_lowercase				) - 1]
																		else:
																								_lowerCAmelCase  						=			False
																								indirect_parents.append(_lowercase				)
																								_lowerCAmelCase  						=			s
																								_lowerCAmelCase  						=			ss

																		# check if se have reached the starting point
																		if len(_lowercase				) == 0:
																								return False




						def  _lowercase     ( self				):

												"""simple docstring"""



												return list(self.graph				)




						def  _lowercase     ( self   ,       _lowercase=-2   ,       _lowercase=-1				):

												"""simple docstring"""



												_lowerCAmelCase  						=			time()
												self.dfs(_lowercase   ,       _lowercase				)
												_lowerCAmelCase  						=			time()
												return end - begin




						def  _lowercase     ( self   ,       _lowercase=-2				):

												"""simple docstring"""



												_lowerCAmelCase  						=			time()
												self.bfs(_lowercase				)
												_lowerCAmelCase  						=			time()
												return end - begin


'''simple docstring'''



from __future__ import annotations

# This is the precision for this function which can be altered.
# It is recommended for users to keep this number greater than or equal to 10.
_lowercase    =		10


def A				(__lowerCamelCase				:int			,     __lowerCamelCase				:int			,     __lowerCamelCase				:list[int]			,     __lowerCamelCase				:int		):
						for i in range(__lowerCamelCase			,     __lowerCamelCase		):
												if array[i] == target:
																		return i
						return -1


def A				(__lowerCamelCase				:list[int]			,     __lowerCamelCase				:int		):
						_lowerCAmelCase  						=			0
						_lowerCAmelCase  						=			len(__lowerCamelCase		)
						while left <= right:
												if right - left < precision:
																		return lin_search(__lowerCamelCase			,     __lowerCamelCase			,     __lowerCamelCase			,     __lowerCamelCase		)

												_lowerCAmelCase  						=			(left + right) // 3 + 1
												_lowerCAmelCase  						=			2 * (left + right) // 3 + 1

												if array[one_third] == target:
																		return one_third
												elif array[two_third] == target:
																		return two_third

												elif target < array[one_third]:
																		_lowerCAmelCase  						=			one_third - 1
												elif array[two_third] < target:
																		_lowerCAmelCase  						=			two_third + 1

												else:
																		_lowerCAmelCase  						=			one_third + 1
																		_lowerCAmelCase  						=			two_third - 1
						else:
												return -1


def A				(__lowerCamelCase				:int			,     __lowerCamelCase				:int			,     __lowerCamelCase				:list[int]			,     __lowerCamelCase				:int		):
						if left < right:
												if right - left < precision:
																		return lin_search(__lowerCamelCase			,     __lowerCamelCase			,     __lowerCamelCase			,     __lowerCamelCase		)
												_lowerCAmelCase  						=			(left + right) // 3 + 1
												_lowerCAmelCase  						=			2 * (left + right) // 3 + 1

												if array[one_third] == target:
																		return one_third
												elif array[two_third] == target:
																		return two_third

												elif target < array[one_third]:
																		return rec_ternary_search(__lowerCamelCase			,     one_third - 1			,     __lowerCamelCase			,     __lowerCamelCase		)
												elif array[two_third] < target:
																		return rec_ternary_search(two_third + 1			,     __lowerCamelCase			,     __lowerCamelCase			,     __lowerCamelCase		)
												else:
																		return rec_ternary_search(one_third + 1			,     two_third - 1			,     __lowerCamelCase			,     __lowerCamelCase		)
						else:
												return -1


if __name__ == "__main__":
						import doctest

						doctest.testmod()

						_lowercase    =		input("""Enter numbers separated by comma:\n""").strip()
						_lowercase    =		[int(item.strip()) for item in user_input.split(""",""")]
						assert collection == sorted(collection), F"List must be ordered.\n{collection}."
						_lowercase    =		int(input("""Enter the number to be found in the list:\n""").strip())
						_lowercase    =		ite_ternary_search(collection, target)
						_lowercase    =		rec_ternary_search(0, len(collection) - 1, collection, target)
						if resulta != -1:
												print(F"""Iterative search: {target} found at positions: {resulta}""")
												print(F"""Recursive search: {target} found at positions: {resulta}""")
						else:
												print("""Not found""")
