






"""simple docstring"""





from __future__ import annotations

import unittest
from collections.abc import Iterator


class   _lowercase			:


      def __init__(     self					:						int				, a					:						int				, a					:						Node | None    ):





            """simple docstring"""







            __snake_case   :     Union[str, Any]	      =label
            __snake_case   :     int	      =parent
            __snake_case   :     Node | None	      =None
            __snake_case   :     Node | None	      =None



class   _lowercase			:


      def __init__(     self					:						List[str]    ):





            """simple docstring"""







            __snake_case   :     Node | None	      =None


      def _UpperCamelCase    (     self					:						str    ):





            """simple docstring"""







            __snake_case   :     List[Any]	      =None


      def _UpperCamelCase    (     self					:						Optional[Any]    ):





            """simple docstring"""







            return self.root is None


      def _UpperCamelCase    (     self					:						Any				, a					:						int    ):





            """simple docstring"""







            __snake_case   :     List[Any]	      =self._put(self.root				, UpperCamelCase_    )


      def _UpperCamelCase    (     self					:						List[Any]				, a					:						Node | None				, a					:						int				, a					:						Node | None = None    ):





            """simple docstring"""







            if node is None:
                  __snake_case   :     Tuple	      =Node(UpperCamelCase_				, UpperCamelCase_    )
            else:
                  if label < node.label:
                        __snake_case   :     List[str]	      =self._put(node.left				, UpperCamelCase_				, UpperCamelCase_    )
                  elif label > node.label:
                        __snake_case   :     Optional[Any]	      =self._put(node.right				, UpperCamelCase_				, UpperCamelCase_    )
                  else:
                        __snake_case   :     str	      =f'''Node with label {label} already exists'''
                        raise Exception(UpperCamelCase_    )

            return node


      def _UpperCamelCase    (     self					:						List[str]				, a					:						int    ):





            """simple docstring"""







            return self._search(self.root				, UpperCamelCase_    )


      def _UpperCamelCase    (     self					:						List[str]				, a					:						Node | None				, a					:						int    ):





            """simple docstring"""







            if node is None:
                  __snake_case   :     int	      =f'''Node with label {label} does not exist'''
                  raise Exception(UpperCamelCase_    )
            else:
                  if label < node.label:
                        __snake_case   :     Tuple	      =self._search(node.left				, UpperCamelCase_    )
                  elif label > node.label:
                        __snake_case   :     List[Any]	      =self._search(node.right				, UpperCamelCase_    )

            return node


      def _UpperCamelCase    (     self					:						str				, a					:						int    ):





            """simple docstring"""







            __snake_case   :     List[str]	      =self.search(UpperCamelCase_    )
            if node.right and node.left:
                  __snake_case   :     int	      =self._get_lowest_node(node.right    )
                  __snake_case   :     List[Any]	      =node.left
                  __snake_case   :     str	      =node.right
                  __snake_case   :     Optional[int]	      =lowest_node
                  if node.right:
                        __snake_case   :     Tuple	      =lowest_node
                  self._reassign_nodes(UpperCamelCase_				, UpperCamelCase_    )
            elif not node.right and node.left:
                  self._reassign_nodes(UpperCamelCase_				, node.left    )
            elif node.right and not node.left:
                  self._reassign_nodes(UpperCamelCase_				, node.right    )
            else:
                  self._reassign_nodes(UpperCamelCase_				, UpperCamelCase_    )


      def _UpperCamelCase    (     self					:						Tuple				, a					:						Node				, a					:						Node | None    ):





            """simple docstring"""







            if new_children:
                  __snake_case   :     Tuple	      =node.parent

            if node.parent:
                  if node.parent.right == node:
                        __snake_case   :     Optional[int]	      =new_children
                  else:
                        __snake_case   :     Dict	      =new_children
            else:
                  __snake_case   :     Tuple	      =new_children


      def _UpperCamelCase    (     self					:						List[Any]				, a					:						Node    ):





            """simple docstring"""







            if node.left:
                  __snake_case   :     Tuple	      =self._get_lowest_node(node.left    )
            else:
                  __snake_case   :     Union[str, Any]	      =node
                  self._reassign_nodes(UpperCamelCase_				, node.right    )

            return lowest_node


      def _UpperCamelCase    (     self					:						str				, a					:						int    ):





            """simple docstring"""







            try:
                  self.search(UpperCamelCase_    )
                  return True
            except Exception:
                  return False


      def _UpperCamelCase    (     self					:						Dict    ):





            """simple docstring"""







            if self.root is None:
                  raise Exception('''Binary search tree is empty'''    )

            __snake_case   :     Optional[int]	      =self.root
            while node.right is not None:
                  __snake_case   :     str	      =node.right

            return node.label


      def _UpperCamelCase    (     self					:						Union[str, Any]    ):





            """simple docstring"""







            if self.root is None:
                  raise Exception('''Binary search tree is empty'''    )

            __snake_case   :     Dict	      =self.root
            while node.left is not None:
                  __snake_case   :     Union[str, Any]	      =node.left

            return node.label


      def _UpperCamelCase    (     self					:						List[str]    ):





            """simple docstring"""







            return self._inorder_traversal(self.root    )


      def _UpperCamelCase    (     self					:						Union[str, Any]				, a					:						Node | None    ):





            """simple docstring"""







            if node is not None:
                  yield from self._inorder_traversal(node.left    )
                  yield node
                  yield from self._inorder_traversal(node.right    )


      def _UpperCamelCase    (     self					:						Optional[Any]    ):





            """simple docstring"""







            return self._preorder_traversal(self.root    )







      def _UpperCamelCase    (     self					:						List[str]				, a					:						Node | None    ):





            """simple docstring"""







            if node is not None:
                  yield node
                  yield from self._preorder_traversal(node.left    )
                  yield from self._preorder_traversal(node.right    )



class   _lowercase			(  unittest.TestCase    ):


      @staticmethod
      def _UpperCamelCase    (     ):





            """simple docstring"""







            __snake_case   :     Dict	      =BinarySearchTree()
            t.put(8    )
            t.put(3    )
            t.put(6    )
            t.put(1    )
            t.put(1_0    )
            t.put(1_4    )
            t.put(1_3    )
            t.put(4    )
            t.put(7    )
            t.put(5    )

            return t


      def _UpperCamelCase    (     self					:						Optional[Any]    ):





            """simple docstring"""







            __snake_case   :     Tuple	      =BinarySearchTree()
            assert t.is_empty()

            t.put(8    )
            assert t.root is not None
            assert t.root.parent is None
            assert t.root.label == 8

            t.put(1_0    )
            assert t.root.right is not None
            assert t.root.right.parent == t.root
            assert t.root.right.label == 1_0

            t.put(3    )
            assert t.root.left is not None
            assert t.root.left.parent == t.root
            assert t.root.left.label == 3

            t.put(6    )
            assert t.root.left.right is not None
            assert t.root.left.right.parent == t.root.left
            assert t.root.left.right.label == 6

            t.put(1    )
            assert t.root.left.left is not None
            assert t.root.left.left.parent == t.root.left
            assert t.root.left.left.label == 1

            with self.assertRaises(UpperCamelCase_    ):  # noqa: B017
                  t.put(1    )


      def _UpperCamelCase    (     self					:						Dict    ):





            """simple docstring"""







            __snake_case   :     List[str]	      =self._get_binary_search_tree()

            __snake_case   :     Optional[int]	      =t.search(6    )
            assert node.label == 6

            __snake_case   :     Optional[int]	      =t.search(1_3    )
            assert node.label == 1_3

            with self.assertRaises(UpperCamelCase_    ):  # noqa: B017
                  t.search(2    )


      def _UpperCamelCase    (     self					:						List[Any]    ):





            """simple docstring"""







            __snake_case   :     Dict	      =self._get_binary_search_tree()

            t.remove(1_3    )
            assert t.root is not None
            assert t.root.right is not None
            assert t.root.right.right is not None
            assert t.root.right.right.right is None
            assert t.root.right.right.left is None

            t.remove(7    )
            assert t.root.left is not None
            assert t.root.left.right is not None
            assert t.root.left.right.left is not None
            assert t.root.left.right.right is None
            assert t.root.left.right.left.label == 4

            t.remove(6    )
            assert t.root.left.left is not None
            assert t.root.left.right.right is not None
            assert t.root.left.left.label == 1
            assert t.root.left.right.label == 4
            assert t.root.left.right.right.label == 5
            assert t.root.left.right.left is None
            assert t.root.left.left.parent == t.root.left
            assert t.root.left.right.parent == t.root.left

            t.remove(3    )
            assert t.root is not None
            assert t.root.left.label == 4
            assert t.root.left.right.label == 5
            assert t.root.left.left.label == 1
            assert t.root.left.parent == t.root
            assert t.root.left.left.parent == t.root.left
            assert t.root.left.right.parent == t.root.left

            t.remove(4    )
            assert t.root.left is not None
            assert t.root.left.left is not None
            assert t.root.left.label == 5
            assert t.root.left.right is None
            assert t.root.left.left.label == 1
            assert t.root.left.parent == t.root
            assert t.root.left.left.parent == t.root.left


      def _UpperCamelCase    (     self					:						Dict    ):





            """simple docstring"""







            __snake_case   :     Union[str, Any]	      =self._get_binary_search_tree()

            t.remove(3    )
            assert t.root is not None
            assert t.root.left is not None
            assert t.root.left.left is not None
            assert t.root.left.right is not None
            assert t.root.left.right.left is not None
            assert t.root.left.right.right is not None
            assert t.root.left.label == 4
            assert t.root.left.right.label == 6
            assert t.root.left.left.label == 1
            assert t.root.left.right.right.label == 7
            assert t.root.left.right.left.label == 5
            assert t.root.left.parent == t.root
            assert t.root.left.right.parent == t.root.left
            assert t.root.left.left.parent == t.root.left
            assert t.root.left.right.left.parent == t.root.left.right


      def _UpperCamelCase    (     self					:						int    ):





            """simple docstring"""







            __snake_case   :     Union[str, Any]	      =self._get_binary_search_tree()
            t.empty()
            assert t.root is None


      def _UpperCamelCase    (     self					:						Union[str, Any]    ):





            """simple docstring"""







            __snake_case   :     int	      =self._get_binary_search_tree()
            assert not t.is_empty()

            t.empty()
            assert t.is_empty()


      def _UpperCamelCase    (     self					:						Tuple    ):





            """simple docstring"""







            __snake_case   :     Tuple	      =self._get_binary_search_tree()

            assert t.exists(6    )
            assert not t.exists(-1    )


      def _UpperCamelCase    (     self					:						str    ):





            """simple docstring"""







            __snake_case   :     int	      =self._get_binary_search_tree()

            assert t.get_max_label() == 1_4

            t.empty()
            with self.assertRaises(UpperCamelCase_    ):  # noqa: B017
                  t.get_max_label()


      def _UpperCamelCase    (     self					:						Union[str, Any]    ):





            """simple docstring"""







            __snake_case   :     Tuple	      =self._get_binary_search_tree()

            assert t.get_min_label() == 1

            t.empty()
            with self.assertRaises(UpperCamelCase_    ):  # noqa: B017
                  t.get_min_label()


      def _UpperCamelCase    (     self					:						str    ):





            """simple docstring"""







            __snake_case   :     List[str]	      =self._get_binary_search_tree()

            __snake_case   :     List[Any]	      =[i.label for i in t.inorder_traversal()]
            assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 1_0, 1_3, 1_4]







      def _UpperCamelCase    (     self					:						Any    ):





            """simple docstring"""







            __snake_case   :     Tuple	      =self._get_binary_search_tree()

            __snake_case   :     Any	      =[i.label for i in t.preorder_traversal()]
            assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 1_0, 1_4, 1_3]



def      __lowercase       (     )       ->       None:
      __snake_case   :     Optional[Any]	      =BinarySearchTree()
      t.put(8			)
      t.put(3			)
      t.put(6			)
      t.put(1			)
      t.put(10			)
      t.put(14			)
      t.put(13			)
      t.put(4			)
      t.put(7			)
      t.put(5			)

      print(
          '''\n            8\n           / \\\n          3   10\n         / \\    \\\n        1   6    14\n           / \\   /\n          4   7 13\n           \\\n            5\n        '''			)

      print('''Label 6 exists:'''							,		t.exists(6			)			)
      print('''Label 13 exists:'''							,		t.exists(13			)			)
      print('''Label -1 exists:'''							,		t.exists(-1			)			)
      print('''Label 12 exists:'''							,		t.exists(12			)			)

      # Prints all the elements of the list in inorder traversal
      __snake_case   :     List[str]	      =[i.label for i in t.inorder_traversal()]
      print('''Inorder traversal:'''							,		a			)

      # Prints all the elements of the list in preorder traversal
      __snake_case   :     List[Any]	      =[i.label for i in t.preorder_traversal()]
      print('''Preorder traversal:'''							,		a			)

      print('''Max. label:'''							,		t.get_max_label()			)
      print('''Min. label:'''							,		t.get_min_label()			)

      # Delete elements
      print('''\nDeleting elements 13, 10, 8, 3, 6, 14'''			)
      print(
          '''\n          4\n         / \\\n        1   7\n             \\\n              5\n        '''			)
      t.remove(13			)
      t.remove(10			)
      t.remove(8			)
      t.remove(3			)
      t.remove(6			)
      t.remove(14			)

      # Prints all the elements of the list in inorder traversal after delete
      __snake_case   :     Optional[Any]	      =[i.label for i in t.inorder_traversal()]
      print('''Inorder traversal after delete:'''							,		a			)

      # Prints all the elements of the list in preorder traversal after delete
      __snake_case   :     Tuple	      =[i.label for i in t.preorder_traversal()]
      print('''Preorder traversal after delete:'''							,		a			)

      print('''Max. label:'''							,		t.get_max_label()			)
      print('''Min. label:'''							,		t.get_min_label()			)


if __name__ == "__main__":
    binary_search_tree_example()








from __future__ import annotations

class   UpperCAmelCase    :






   def __init__(						self :							List[Any]    ,       UpperCamelCase_ :							int  )->      None:
     _lowercase:			Optional[Any]      =     data
     _lowercase:			Optional[int]      =     None

class   UpperCAmelCase    :






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






   def 			_a    (						self :							List[Any]    ,       UpperCamelCase_ :							int  )->      int:
     _lowercase:			Any      =     Node(UpperCamelCase_  )
     _lowercase:			List[Any]      =     self.head
     _lowercase:			List[str]      =     new_node
     return self.head.data






   def 			_a    (						self :							Tuple  )->      int | None:
     _lowercase:			List[str]      =     self.head
     _lowercase:			str      =     self.head
     if self.head:
       while fast_pointer and fast_pointer.next:
         _lowercase:			Optional[int]      =     fast_pointer.next.next
         _lowercase:			Tuple      =     slow_pointer.next
       return slow_pointer.data
     else:
       print('No element found.'  )
       return None


if __name__ == "__main__":
   UpperCAmelCase__    :							Union[str, Any]       		=     LinkedList()
   for _ in range(int(input().strip())):
      UpperCAmelCase__    :							List[Any]       		=     int(input().strip())
      link.push(data)
   print(link.middle_element())
