



"""simple docstring"""
from multiprocessing import Lock, Pipe, Process

# lock used to ensure that two processes do not access a pipe at the same time
A:   Optional[Any]								=		Lock()

def       _snake_case						(						UpperCamelCase						:		Tuple			,		UpperCamelCase						:		Optional[int]			,		UpperCamelCase						:		List[str]			,		UpperCamelCase						:		int			,		UpperCamelCase						:		str			,		UpperCamelCase						:		Dict			,		UpperCamelCase						:		str						):
 global process_lock

 # we perform n swaps since after n swaps we know we are sorted
 # we *could* stop early if we are sorted already, but it takes as long to
 # find out we are sorted as it does to sort the list with this algorithm
 for i in range(0			,		10						):
  if (i + position) % 2 == 0 and r_send is not None:
   # send your value to your right neighbor
   process_lock.acquire()
   r_send[1].send(UpperCamelCase						)
   process_lock.release()

   # receive your right neighbor's value
   process_lock.acquire()
   UpperCAmelCase	:					Optional[Any]	=	rr_cv[0].recv()
   process_lock.release()

   # take the lower value since you are on the left
   UpperCAmelCase	:					List[Any]	=	min(UpperCamelCase			,		UpperCamelCase						)
  elif (i + position) % 2 != 0 and l_send is not None:
   # send your value to your left neighbor
   process_lock.acquire()
   l_send[1].send(UpperCamelCase						)
   process_lock.release()

   # receive your left neighbor's value
   process_lock.acquire()
   UpperCAmelCase	:					str	=	lr_cv[0].recv()
   process_lock.release()

   # take the higher value since you are on the right
   UpperCAmelCase	:					List[str]	=	max(UpperCamelCase			,		UpperCamelCase						)
    # after all swaps are performed, send the values back to main
 result_pipe[1].send(UpperCamelCase						)

def       _snake_case						(						UpperCamelCase						:		Optional[int]						):
 UpperCAmelCase	:					Tuple	=	[]
 UpperCAmelCase	:					List[str]	=	[]
 # initialize the list of pipes where the values will be retrieved
 for _ in arr:
  result_pipe.append(Pipe()						)
 # creates the processes
 # the first and last process only have one neighbor so they are made outside
 # of the loop
 UpperCAmelCase	:					Optional[Any]	=	Pipe()
 UpperCAmelCase	:					Optional[int]	=	Pipe()
 process_array_.append(
     Process(
         target=UpperCamelCase			,		args=(0, arr[0], None, temp_rs, None, temp_rr, result_pipe[0])			,		)						)
 UpperCAmelCase	:					int	=	temp_rs
 UpperCAmelCase	:					Optional[Any]	=	temp_rr

 for i in range(1			,		len(UpperCamelCase						) - 1						):
  UpperCAmelCase	:					Optional[Any]	=	Pipe()
  UpperCAmelCase	:					Tuple	=	Pipe()
  process_array_.append(
      Process(
          target=UpperCamelCase			,		args=(i, arr[i], temp_ls, temp_rs, temp_lr, temp_rr, result_pipe[i])			,		)						)
  UpperCAmelCase	:					Optional[int]	=	temp_rs
  UpperCAmelCase	:					Optional[int]	=	temp_rr

 process_array_.append(
     Process(
         target=UpperCamelCase			,		args=(
             len(UpperCamelCase						) - 1,
             arr[len(UpperCamelCase						) - 1],
             temp_ls,
             None,
             temp_lr,
             None,
             result_pipe[len(UpperCamelCase						) - 1],
         )			,		)						)

 # start the processes
 for p in process_array_:
  p.start()

 # wait for the processes to end and write their values to the list
 for p in range(0			,		len(UpperCamelCase						)						):
  UpperCAmelCase	:					str	=	result_pipe[p][0].recv()
  process_array_[p].join()
 return arr

def       _snake_case						(						):
 UpperCAmelCase	:					Dict	=	list(range(10			,		0			,		-1						)						)
 print("""Initial List"""						)
 print(*UpperCamelCase						)
 UpperCAmelCase	:					int	=	odd_even_transposition(UpperCamelCase						)
 print("""Sorted List\n"""						)
 print(*UpperCamelCase						)


if __name__ == "__main__":
      main()





"""simple docstring"""
A:   int								=		range(2, 2_0 + 1)
A:   Any								=		[1_0**k for k in range(ks[-1] + 1)]
A:   dict[int, dict[int, list[list[int]]]]								=		{}

def       _snake_case						(						UpperCamelCase						:		Dict			,		UpperCamelCase						:		Any			,		UpperCamelCase						:		Any			,		UpperCamelCase						:		int						):
 UpperCAmelCase	:					List[str]	=	sum(a_i[j] for j in range(UpperCamelCase			,		len(UpperCamelCase						)						)						)
 UpperCAmelCase	:					str	=	sum(a_i[j] * base[j] for j in range(min(len(UpperCamelCase						)			,		UpperCamelCase						)						)						)

 UpperCAmelCase	,		UpperCAmelCase	:					str	=	0, 0
 UpperCAmelCase	:					Optional[Any]	=	n - i

 UpperCAmelCase	:					Optional[int]	=	memo.get(UpperCamelCase						)

 if sub_memo is not None:
  UpperCAmelCase	:					str	=	sub_memo.get(UpperCamelCase						)

  if jumps is not None and len(UpperCamelCase						) > 0:
   # find and make the largest jump without going over
   UpperCAmelCase	:					Tuple	=	-1
   for _k in range(len(UpperCamelCase						) - 1			,		-1			,		-1						):
    if jumps[_k][2] <= k and jumps[_k][1] <= max_dn:
     UpperCAmelCase	:					int	=	_k
     break

   if max_jump >= 0:
    UpperCAmelCase	,		UpperCAmelCase	,		UpperCAmelCase	:					Optional[Any]	=	jumps[max_jump]
    # since the difference between jumps is cached, add c
    UpperCAmelCase	:					List[str]	=	diff + c
    for j in range(min(UpperCamelCase			,		len(UpperCamelCase						)						)						):
     UpperCAmelCase	,		UpperCAmelCase	:					Union[str, Any]	=	divmod(UpperCamelCase			,		10						)
    if new_c > 0:
     add(UpperCamelCase			,		UpperCamelCase			,		UpperCamelCase						)

  else:
   UpperCAmelCase	:					int	=	[]
 else:
  UpperCAmelCase	:					List[str]	=	{c: []}
  UpperCAmelCase	:					str	=	sub_memo

 if dn >= max_dn or c + diff >= base[k]:
  return diff, dn

 if k > ks[0]:
  while True:
   # keep doing smaller jumps
   UpperCAmelCase	,		UpperCAmelCase	:					List[str]	=	next_term(UpperCamelCase			,		k - 1			,		i + dn			,		UpperCamelCase						)
   diff += _diff
   dn += terms_jumped

   if dn >= max_dn or c + diff >= base[k]:
    break
 else:
  # would be too small a jump, just compute sequential terms instead
  UpperCAmelCase	,		UpperCAmelCase	:					int	=	compute(UpperCamelCase			,		UpperCamelCase			,		i + dn			,		UpperCamelCase						)
  diff += _diff
  dn += terms_jumped

 UpperCAmelCase	:					Dict	=	sub_memo[c]

 # keep jumps sorted by # of terms skipped
 UpperCAmelCase	:					str	=	0
 while j < len(UpperCamelCase						):
  if jumps[j][1] > dn:
   break
  j += 1

 # cache the jump for this value digitsum(b) and c
 sub_memo[c].insert(UpperCamelCase			,		(diff, dn, k)						)
 return (diff, dn)

def       _snake_case						(						UpperCamelCase						:		int			,		UpperCamelCase						:		Tuple			,		UpperCamelCase						:		Union[str, Any]			,		UpperCamelCase						:		Any						):
 if i >= n:
  return 0, i
 if k > len(UpperCamelCase						):
  a_i.extend([0 for _ in range(k - len(UpperCamelCase						)						)]						)

 # note: a_i -> b * 10^k + c
 # ds_b -> digitsum(b)
 # ds_c -> digitsum(c)
 UpperCAmelCase	:					List[str]	=	i
 UpperCAmelCase	,		UpperCAmelCase	,		UpperCAmelCase	:					Optional[int]	=	0, 0, 0
 for j in range(len(UpperCamelCase						)						):
  if j >= k:
   ds_b += a_i[j]
  else:
   ds_c += a_i[j]

 while i < n:
  i += 1
  UpperCAmelCase	:					Optional[int]	=	ds_c + ds_b
  diff += addend
  UpperCAmelCase	:					str	=	0
  for j in range(UpperCamelCase						):
   UpperCAmelCase	:					Any	=	a_i[j] + addend
   UpperCAmelCase	,		UpperCAmelCase	:					Any	=	divmod(UpperCamelCase			,		10						)

   ds_c += a_i[j]

  if addend > 0:
   break

 if addend > 0:
  add(UpperCamelCase			,		UpperCamelCase			,		UpperCamelCase						)
 return diff, i - start_i

def       _snake_case						(						UpperCamelCase						:		Union[str, Any]			,		UpperCamelCase						:		str			,		UpperCamelCase						:		Optional[int]						):
 for j in range(UpperCamelCase			,		len(UpperCamelCase						)						):
  UpperCAmelCase	:					Optional[int]	=	digits[j] + addend
  if s >= 10:
   UpperCAmelCase	,		UpperCAmelCase	:					int	=	divmod(UpperCamelCase			,		10						)
   UpperCAmelCase	:					str	=	addend // 10 + quotient
  else:
   UpperCAmelCase	:					Any	=	s
   UpperCAmelCase	:					Union[str, Any]	=	addend // 10

  if addend == 0:
   break

 while addend > 0:
  UpperCAmelCase	,		UpperCAmelCase	:					Any	=	divmod(UpperCamelCase			,		10						)
  digits.append(UpperCamelCase						)

def       _snake_case						(						UpperCamelCase						:		int = 10**15						):
 UpperCAmelCase	:					Dict	=	[1]
 UpperCAmelCase	:					int	=	1
 UpperCAmelCase	:					Tuple	=	0
 while True:
  UpperCAmelCase	,		UpperCAmelCase	:					Tuple	=	next_term(UpperCamelCase			,		20			,		i + dn			,		UpperCamelCase						)
  dn += terms_jumped
  if dn == n - i:
   break

 UpperCAmelCase	:					Any	=	0
 for j in range(len(UpperCamelCase						)						):
  a_n += digits[j] * 10**j
 return a_n


if __name__ == "__main__":
      print(f"""{solution() = }""")
