





from __future__ import annotations







class 						_lowerCAmelCase:

  """simple docstring"""







  def __init__( self  ,    UpperCAmelCase     )-> None:
     __A				 =       data
     __A				 =       None







class 						_lowerCAmelCase:

  """simple docstring"""







  def __init__( self     )-> Dict:
     __A				 =       None

  def 		SCREAMING_SNAKE_CASE__	( self  ,    UpperCAmelCase     )-> int:
     __A				 =       Node(UpperCamelCase__     )
     __A				 =       self.head
     __A				 =       new_node
     return self.head.data





  def 		SCREAMING_SNAKE_CASE__	( self     )-> int | None:
     __A				 =       self.head
     __A				 =       self.head
     if self.head:
        while fast_pointer and fast_pointer.next:
           __A				 =       fast_pointer.next.next
           __A				 =       slow_pointer.next
        return slow_pointer.data
     else:
        print('''No element found.'''     )
        return None


if __name__ == "__main__":
 _UpperCamelCase   :							str     =	LinkedList()
 for _ in range(int(input().strip())):
  _UpperCamelCase   :							Any     =	int(input().strip())
  link.push(data)
 print(link.middle_element())








from __future__ import annotations
def 				__UpperCamelCase  (		snake_case    ,	snake_case     )  ->						list:


   '''simple docstring'''







   __A				 =       [None] * (len(snake_case     ) + len(snake_case     ))

   __A				 =       0  # pointer to current index for left Half
   __A				 =       0  # pointer to current index for the right Half
   __A				 =       0  # pointer to current index for the sorted array Half

   while pointera < len(snake_case     ) and pointera < len(snake_case     ):
      if left_half[pointera] < right_half[pointera]:
         __A				 =       left_half[pointera]
         pointera += 1
         index += 1
      else:
         __A				 =       right_half[pointera]
         pointera += 1
         index += 1
   while pointera < len(snake_case     ):
      __A				 =       left_half[pointera]
      pointera += 1
      index += 1

   while pointera < len(snake_case     ):
      __A				 =       right_half[pointera]
      pointera += 1
      index += 1

   return sorted_array
def 				__UpperCamelCase  (		snake_case     )  ->						list:


   '''simple docstring'''







   if len(snake_case     ) <= 1:
      return array
   # the actual formula to calculate the middle element = left + (right - left) // 2
   # this avoids integer overflow in case of large N
   __A				 =       0 + (len(snake_case     ) - 0) // 2

   # Split the array into halves till the array length becomes equal to One
   # merge the arrays of single length returned by mergeSort function and
   # pass them into the merge arrays function which merges the array
   __A				 =       array[:middle]
   __A				 =       array[middle:]

   return merge(merge_sort(snake_case     )    ,	merge_sort(snake_case     )     )


if __name__ == "__main__":
    import doctest

    doctest.testmod()

