
'''simple docstring'''

def        UpperCAmelCase_ (  lowerCamelCase_			):







 """simple docstring"""


 lowerCAmelCase__     :   int     		=	0
 lowerCAmelCase__     :   Optional[Any]     		=	len(lowerCamelCase_			)

 for i in range(n - 1			):
  for j in range(i + 1      ,			lowerCamelCase_			):
   if arr[i] > arr[j]:
    num_inversions += 1

 return num_inversions


def        UpperCAmelCase_ (  lowerCamelCase_			):







 """simple docstring"""


 if len(lowerCamelCase_			) <= 1:
  return arr, 0
 lowerCAmelCase__     :   str     		=	len(lowerCamelCase_			) // 2
 lowerCAmelCase__     :   Optional[Any]     		=	arr[0:mid]
 lowerCAmelCase__     :   Any     		=	arr[mid:]

 lowerCAmelCase__		,     lowerCAmelCase__     :   Optional[int]     		=	count_inversions_recursive(lowerCamelCase_			)
 lowerCAmelCase__		,     lowerCAmelCase__     :   Dict     		=	count_inversions_recursive(lowerCamelCase_			)
 lowerCAmelCase__		,     lowerCAmelCase__     :   Optional[Any]     		=	_count_cross_inversions(lowerCamelCase_      ,			lowerCamelCase_			)

 lowerCAmelCase__     :   Optional[int]     		=	inversion_p + inversions_q + cross_inversions
 return c, num_inversions


def        UpperCAmelCase_ (  lowerCamelCase_      ,			lowerCamelCase_			):







 """simple docstring"""


 lowerCAmelCase__     :   Dict     		=	[]
 lowerCAmelCase__     :   List[str]     		=	0
 while i < len(lowerCamelCase_			) and j < len(lowerCamelCase_			):
  if p[i] > q[j]:
   # if P[1] > Q[j], then P[k] > Q[k] for all  i < k <= len(P)
   # These are all inversions. The claim emerges from the
   # property that P is sorted.
   num_inversion += len(lowerCamelCase_			) - i
   r.append(q[j]			)
   j += 1
  else:
   r.append(p[i]			)
   i += 1

 if i < len(lowerCamelCase_			):
  r.extend(p[i:]			)
 else:
  r.extend(q[j:]			)

 return r, num_inversion


def        UpperCAmelCase_ (  ):







 """simple docstring"""


 lowerCAmelCase__     :   str     		=	[1_0, 2, 1, 5, 5, 2, 1_1]

 # this arr has 8 inversions:
 # (10, 2), (10, 1), (10, 5), (10, 5), (10, 2), (2, 1), (5, 2), (5, 2)

 lowerCAmelCase__     :   List[Any]     		=	count_inversions_bf(lowerCamelCase_			)
 lowerCAmelCase__		,     lowerCAmelCase__     :   Optional[Any]     		=	count_inversions_recursive(lowerCamelCase_			)

 assert num_inversions_bf == num_inversions_recursive == 8

 print("number of inversions = "      ,			lowerCamelCase_			)

 # testing an array with zero inversion (a sorted arr_1)

 arr_a.sort()
 lowerCAmelCase__     :   Any     		=	count_inversions_bf(lowerCamelCase_			)
 lowerCAmelCase__		,     lowerCAmelCase__     :   Tuple     		=	count_inversions_recursive(lowerCamelCase_			)

 assert num_inversions_bf == num_inversions_recursive == 0
 print("number of inversions = "      ,			lowerCamelCase_			)

 # an empty list should also have zero inversions
 lowerCAmelCase__     :   Dict     		=	[]
 lowerCAmelCase__     :   Any     		=	count_inversions_bf(lowerCamelCase_			)
 lowerCAmelCase__		,     lowerCAmelCase__     :   Optional[int]     		=	count_inversions_recursive(lowerCamelCase_			)

 assert num_inversions_bf == num_inversions_recursive == 0
 print("number of inversions = "      ,			lowerCamelCase_			)


if __name__ == "__main__":
     main()







'''simple docstring'''

def        UpperCAmelCase_ (  lowerCamelCase_      ,			lowerCamelCase_      ,			lowerCamelCase_      ,			lowerCamelCase_			):







 """simple docstring"""


 if height >= 1:
  move_tower(height - 1      ,			lowerCamelCase_      ,			lowerCamelCase_      ,			lowerCamelCase_			)
  move_disk(lowerCamelCase_      ,			lowerCamelCase_			)
  move_tower(height - 1      ,			lowerCamelCase_      ,			lowerCamelCase_      ,			lowerCamelCase_			)


def        UpperCAmelCase_ (  lowerCamelCase_      ,			lowerCamelCase_			):







 """simple docstring"""


 print("moving disk from"      ,			lowerCamelCase_      ,			"to"      ,			lowerCamelCase_			)


def        UpperCAmelCase_ (  ):







 """simple docstring"""


 lowerCAmelCase__     :   List[str]     		=	int(input("Height of hanoi: "			).strip()			)
 move_tower(lowerCamelCase_      ,			"A"      ,			"B"      ,			"C"			)


if __name__ == "__main__":
     main()





