



class 		_lowercase		:

   def __init__(   self      :							Any				, __lowerCAmelCase      :							List[Any]				)							->					Dict:


    """simple docstring"""






    a							=		val
    # Number of nodes in left subtree
    a							=		0
    a							=		None
    a							=		None
    a							=		None




   def 		A				(   self      :							Any				, __lowerCAmelCase      :							List[Any]				)							->					str:


    """simple docstring"""






    assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

    if self.val < other.val:
     a							=		self.right
     a							=		None
     if self.right:
      a							=		other
     a							=		other
     a							=		self.left_tree_size * 2 + 1
     return self
    else:
     a							=		other.right
     a							=		None
     if other.right:
      a							=		self
     a							=		self
     a							=		other.left_tree_size * 2 + 1
     return other



class 		_lowercase		:

   def __init__(   self      :							str				, __lowerCAmelCase      :							str=None				, __lowerCAmelCase      :							Union[str, Any]=None				, __lowerCAmelCase      :							List[Any]=0				)							->					List[Any]:


    """simple docstring"""






    a							=		heap_size
    a							=		bottom_root
    a							=		min_node

   def 		A				(   self      :							int				, __lowerCAmelCase      :							Any				)							->					str:


    """simple docstring"""






    if other.size == 0:
     return None
    if self.size == 0:
     a							=		other.size
     a							=		other.bottom_root
     a							=		other.min_node
     return None
    # Update size
    a							=		self.size + other.size

    # Update min.node
    if self.min_node.val > other.min_node.val:
     a							=		other.min_node
    # Merge

    # Order roots by left_subtree_size
    a							=		[]
    a		,	a							=		self.bottom_root, other.bottom_root
    while i or j:
     if i and ((not j) or i.left_tree_size < j.left_tree_size):
      combined_roots_list.append((i, True)				)
      a							=		i.parent
     else:
      combined_roots_list.append((j, False)				)
      a							=		j.parent
        # Insert links between them
    for i in range(len(__lowerCAmelCase				) - 1				):
     if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
      a							=		combined_roots_list[i + 1][0]
      a							=		combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
    a							=		combined_roots_list[0][0]
    while i.parent:
     if (
         (i.left_tree_size == i.parent.left_tree_size) and (not i.parent.parent)
     ) or (
         i.left_tree_size == i.parent.left_tree_size
         and i.left_tree_size != i.parent.parent.left_tree_size
     ):
      # Neighbouring Nodes
      a							=		i.left
      a							=		i.parent.parent

      # Merging trees
      a							=		i.merge_trees(i.parent				)

      # Updating links
      a							=		previous_node
      a							=		next_node
      if previous_node:
       a							=		i
      if next_node:
       a							=		i
     else:
      a							=		i.parent
        # Updating self.bottom_root
    while i.left:
     a							=		i.left
    a							=		i

    # Update other
    a							=		self.size
    a							=		self.bottom_root
    a							=		self.min_node

    # Return the merged heap
    return self

   def 		A				(   self      :							Union[str, Any]				, __lowerCAmelCase      :							List[str]				)							->					Optional[int]:


    """simple docstring"""






    if self.size == 0:
     a							=		Node(__lowerCAmelCase				)
     a							=		1
     a							=		self.bottom_root
    else:
     # Create new node
     a							=		Node(__lowerCAmelCase				)

     # Update size
     self.size += 1

     # update min_node
     if val < self.min_node.val:
      a							=		new_node
     # Put new_node as a bottom_root in heap
     a							=		new_node
     a							=		self.bottom_root
     a							=		new_node

     # Consecutively merge roots with same left_tree_size
     while (
         self.bottom_root.parent
         and self.bottom_root.left_tree_size
         == self.bottom_root.parent.left_tree_size
     ):
      # Next node
      a							=		self.bottom_root.parent.parent

      # Merge
      a							=		self.bottom_root.merge_trees(self.bottom_root.parent				)

      # Update Links
      a							=		next_node
      a							=		None
      if next_node:
       a							=		self.bottom_root

   def 		A				(   self      :							List[str]				)							->					str:


    """simple docstring"""






    return self.min_node.val

   def 		A				(   self      :							List[Any]				)							->					List[Any]:


    """simple docstring"""






    return self.size == 0

   def 		A				(   self      :							List[Any]				)							->					Any:


    """simple docstring"""






    a							=		self.min_node.val

    # Last element in heap corner case
    if self.size == 1:
     # Update size
     a							=		0

     # Update bottom root
     a							=		None

     # Update min_node
     a							=		None

     return min_value
    # No right subtree corner case
    # The structure of the tree implies that this should be the bottom root
    # and there is at least one other root
    if self.min_node.right is None:
     # Update size
     self.size -= 1

     # Update bottom root
     a							=		self.bottom_root.parent
     a							=		None

     # Update min_node
     a							=		self.bottom_root
     a							=		self.bottom_root.parent
     while i:
      if i.val < self.min_node.val:
       a							=		i
      a							=		i.parent
     return min_value
    # General case
    # Find the BinomialHeap of the right subtree of min_node
    a							=		self.min_node.right
    a							=		None
    a							=		bottom_of_new
    a							=		1

    # Size, min_node and bottom_root
    while bottom_of_new.left:
     a							=		size_of_new * 2 + 1
     a							=		bottom_of_new.left
     if bottom_of_new.val < min_of_new.val:
      a							=		bottom_of_new
        # Corner case of single root on top left path
    if (not self.min_node.left) and (not self.min_node.parent):
     a							=		size_of_new
     a							=		bottom_of_new
     a							=		min_of_new
     # print("Single root, multiple nodes case")
     return min_value
    # Remaining cases
    # Construct heap of right subtree
    a							=		BinomialHeap(
        bottom_root=__lowerCAmelCase				, min_node=__lowerCAmelCase				, heap_size=__lowerCAmelCase				)

    # Update size
    a							=		self.size - 1 - size_of_new

    # Neighbour nodes
    a							=		self.min_node.left
    a							=		self.min_node.parent

    # Initialize new bottom_root and min_node
    a							=		previous_node or next_node
    a							=		next_node

    # Update links of previous_node and search below for new min_node and
    # bottom_root
    if previous_node:
     a							=		next_node

     # Update bottom_root and search for min_node below
     a							=		previous_node
     a							=		previous_node
     while self.bottom_root.left:
      a							=		self.bottom_root.left
      if self.bottom_root.val < self.min_node.val:
       a							=		self.bottom_root
    if next_node:
     a							=		previous_node

     # Search for new min_node above min_node
     a							=		next_node
     while i:
      if i.val < self.min_node.val:
       a							=		i
      a							=		i.parent
        # Merge heaps
    self.merge_heaps(__lowerCAmelCase				)

    return min_value

   def 		A				(   self      :							Optional[int]				)							->					Optional[Any]:


    """simple docstring"""






    a							=		self.bottom_root
    while top_root.parent:
     a							=		top_root.parent
    # preorder
    a							=		[]
    self.__traversal(__lowerCAmelCase				, __lowerCAmelCase				)
    return heap_pre_order

   def 		A				(   self      :							List[Any]				, __lowerCAmelCase      :							Any				, __lowerCAmelCase      :							Any				, __lowerCAmelCase      :							List[str]=0				)							->					Tuple:


    """simple docstring"""






    if curr_node:
     preorder.append((curr_node.val, level)				)
     self.__traversal(curr_node.left				, __lowerCAmelCase				, level + 1				)
     self.__traversal(curr_node.right				, __lowerCAmelCase				, level + 1				)
    else:
     preorder.append(("#", level)				)




   def __str__(   self      :							Optional[int]				)							->					int:


    """simple docstring"""






    if self.is_empty():
     return ""
    a							=		self.pre_order()

    return "\n".join(("-" * level + str(__lowerCAmelCase				)) for value, level in preorder_heap				)


# Unit Tests
if __name__ == "__main__":
     import doctest

     doctest.testmod()






from collections import Counter


def 						UpperCAmelCase__   (   UpperCAmelCase__			:list[int]       ):






 '''simple docstring'''

 return sum(socks_by_color // 2 for socks_by_color in Counter(UpperCAmelCase__       ).values()       )


if __name__ == "__main__":
     import doctest

     doctest.testmod()

     A_		:  List[str]										=  [int(x) for x in input('''Enter socks by color :''').rstrip().split()]
     print(F"""sock_merchant({colors}) = {sock_merchant(colors)}""")

