





def        __lowercase       (				_SCREAMING_SNAKE_CASE     )			->       Union[str, Any]:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE		=						0
      SCREAMING_SNAKE_CASE		=						len(_SCREAMING_SNAKE_CASE     )

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

      return num_inversions



def        __lowercase       (				_SCREAMING_SNAKE_CASE     )			->       Optional[Any]:


      '''simple docstring'''


      if len(_SCREAMING_SNAKE_CASE     ) <= 1:
            return arr, 0
      SCREAMING_SNAKE_CASE		=						len(_SCREAMING_SNAKE_CASE     ) // 2
      SCREAMING_SNAKE_CASE		=						arr[0:mid]
      SCREAMING_SNAKE_CASE		=						arr[mid:]

      SCREAMING_SNAKE_CASE, SCREAMING_SNAKE_CASE		=						count_inversions_recursive(_SCREAMING_SNAKE_CASE     )
      SCREAMING_SNAKE_CASE, SCREAMING_SNAKE_CASE		=						count_inversions_recursive(_SCREAMING_SNAKE_CASE     )
      SCREAMING_SNAKE_CASE, SCREAMING_SNAKE_CASE		=						_count_cross_inversions(_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE     )

      SCREAMING_SNAKE_CASE		=						inversion_p + inversions_q + cross_inversions
      return c, num_inversions



def        __lowercase       (				_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE     )			->       int:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE		=						[]
      SCREAMING_SNAKE_CASE		=						SCREAMING_SNAKE_CASE		=						SCREAMING_SNAKE_CASE		=						0
      while i < len(_SCREAMING_SNAKE_CASE     ) and j < len(_SCREAMING_SNAKE_CASE     ):
            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(_SCREAMING_SNAKE_CASE     ) - i
                  r.append(q[j]     )
                  j += 1
            else:
                  r.append(p[i]     )
                  i += 1

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

      return r, num_inversion



def        __lowercase       (				)			->       Tuple:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE		=						[10, 2, 1, 5, 5, 2, 11]

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

      SCREAMING_SNAKE_CASE		=						count_inversions_bf(_SCREAMING_SNAKE_CASE     )
      SCREAMING_SNAKE_CASE, SCREAMING_SNAKE_CASE		=						count_inversions_recursive(_SCREAMING_SNAKE_CASE     )

      assert num_inversions_bf == num_inversions_recursive == 8

      print("""number of inversions = """			,						_SCREAMING_SNAKE_CASE     )

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

      arr_a.sort()
      SCREAMING_SNAKE_CASE		=						count_inversions_bf(_SCREAMING_SNAKE_CASE     )
      SCREAMING_SNAKE_CASE, SCREAMING_SNAKE_CASE		=						count_inversions_recursive(_SCREAMING_SNAKE_CASE     )

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

      # an empty list should also have zero inversions
      SCREAMING_SNAKE_CASE		=						[]
      SCREAMING_SNAKE_CASE		=						count_inversions_bf(_SCREAMING_SNAKE_CASE     )
      SCREAMING_SNAKE_CASE, SCREAMING_SNAKE_CASE		=						count_inversions_recursive(_SCREAMING_SNAKE_CASE     )

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


if __name__ == "__main__":
      main()









class 		UpperCamelCase__			:



     '''simple docstring'''

     def __init__(							self						:   int	)					->		str:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						{}






     def     SCREAMING_SNAKE_CASE__  (							self						:   List[Any]	)					->		None:




           '''simple docstring'''


           print(self.vertex	)
           for i in self.vertex:
                 print(lowerCamelCase__						,""" -> """						,""" -> """.join([str(lowerCamelCase__	) for j in self.vertex[i]]	)	)






     def     SCREAMING_SNAKE_CASE__  (							self						:   List[Any]						,lowerCamelCase__						:   int						,lowerCamelCase__						:   int	)					->		None:




           '''simple docstring'''


           if from_vertex in self.vertex:
                 self.vertex[from_vertex].append(lowerCamelCase__	)
           else:
                 # else make a new vertex
                 SCREAMING_SNAKE_CASE		=						[to_vertex]






     def     SCREAMING_SNAKE_CASE__  (							self						:   str	)					->		None:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						[False] * len(self.vertex	)

           # call the recursive helper function
           for i in range(len(self.vertex	)	):
                 if not visited[i]:
                       self.dfs_recursive(lowerCamelCase__						,lowerCamelCase__	)






     def     SCREAMING_SNAKE_CASE__  (							self						:   Any						,lowerCamelCase__						:   int						,lowerCamelCase__						:   list	)					->		None:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						True

           print(lowerCamelCase__						,end=""" """	)

           # Recur for all the vertices that are adjacent to this node
           for i in self.vertex:
                 if not visited[i]:
                       self.dfs_recursive(lowerCamelCase__						,lowerCamelCase__	)


if __name__ == "__main__":
      SCREAMING_SNAKE_CASE_						       =	Graph()
      g.add_edge(0, 1)
      g.add_edge(0, 2)
      g.add_edge(1, 2)
      g.add_edge(2, 0)
      g.add_edge(2, 3)
      g.add_edge(3, 3)

      g.print_graph()
      print("""DFS:""")
      g.dfs()

      # OUTPUT:
      # 0  ->  1 -> 2
      # 1  ->  2
      # 2  ->  0 -> 3
      # 3  ->  3
      # DFS:
      #  0 1 2 3


