class Node:
  R=True
  B=False
  def __init__(self, key, color=R):
    if not type(color)==bool:
      raise TypeError("Bad color")
    self.color=color
    self.key=key
    self.left=self.right=self.parent=NilNode.instance()
  def __str__(self,level=0,indent="   "):
    s=level*indent+str(self.key)
    if self.left:
      s=s + "\n" + self.left.__str__(level + 1, indent)
    if self.right:
      s=s + "\n" + self.right.__str__(level + 1, indent)
    return s
  def __nonzero__(self):
    return True
  def __bool__(self):
    return True

class NilNode(Node):
  __instance__=None
  @classmethod
  def instance(self):
    if self.__instance__ is None:
      self.__instance__=NilNode()
    return self.__instance__
  def __init__(self):
    self.color=Node.B
    self.key=None
    self.left=self.right=self.parent=None
  def __nonzero__(self):
    return False
  def __bool__(self):
    return False

class RedBlackTree:
  def __init__(self):
    self.root=NilNode.instance()
    self.size=0
  def __str__(self):
    return ("(root.size=%d)\n" % self.size)  + str(self.root)
  def add(self, key):
    self.insert(Node(key))
  def remove(self,a):
    self.delete(Node(a))
  def insert(self,x):
    self.__insert_helper(x)
    x.color=Node.R
    while x != self.root and x.parent.color==Node.R:
      if x.parent==x.parent.parent.left:
        y=x.parent.parent.right
        if y and y.color==Node.R:
          x.parent.color=Node.B
          y.color=Node.B
          x.parent.parent.color=Node.R
          x=x.parent.parent
        else:
          if x==x.parent.right:
            x=x.parent
            self.__left_rotate(x)
          x.parent.color=Node.B
          x.parent.parent.color=Node.R
          self.__right_rotate(x.parent.parent)
      else:
        y=x.parent.parent.left
        if y and y.color==Node.R:
          x.parent.color=Node.B
          y.color=Node.B
          x.parent.parent.color=Node.R
          x=x.parent.parent
        else:
          if x==x.parent.left:
            x=x.parent
            self.__right_rotate(x)
          x.parent.color=Node.B
          x.parent.parent.color=Node.R
          self.__left_rotate(x.parent.parent)
    self.root.color=Node.B
    
  def delete(self, z):
    if not z.left or not z.right:
      y=z
    else:
      y=self.successor(z)
    if not y.left:
      x=y.right
    else:
      x=y.left
    x.parent=y.parent
    
    if not y.parent:
      self.root=x
    else:
      if y==y.parent.left:
        y.parent.left=x
      else:
        y.parent.right=x
    if y != z: z.key=y.key
    if y.color==Node.B:
      self.__delete_fixup(x)

    self.size -= 1
    return y
  def minimum(self, x=None):
    if x is None: x=self.root
    while x.left:
      x=x.left
    return x
  def maximum(self, x=None):
    if x is None: x=self.root
    while x.right:
      x=x.right
    return x
  def successor(self, x):
    if x.right:
      return self.minimum(x.right)
    y=x.parent
    while y and x==y.right:
      x=y
      y=y.parent
    return y
  
  def is_empty(self):
    return bool(self.root)

  def __left_rotate(self, x):
    if not x.right:
      raise "x.right is nil!"
    y=x.right
    x.right=y.left
    if y.left: y.left.parent=x
    y.parent=x.parent
    if not x.parent:
      self.root=y
    else:
      if x==x.parent.left:
        x.parent.left=y
      else:
        x.parent.right=y
    y.left=x
    x.parent=y

  def __right_rotate(self, x):
    if not x.left:
      raise "x.left is nil!"
    y=x.left
    x.left=y.right
    if y.right: y.right.parent=x
    y.parent=x.parent
    if not x.parent:
      self.root=y
    else:
      if x==x.parent.left:
        x.parent.left=y
      else:
        x.parent.right=y
    y.right=x
    x.parent=y

  def __insert_helper(self, z):
    y=NilNode.instance()
    x=self.root
    while x:
      y=x
      if z.key < x.key:
        x=x.left
      else:
        x=x.right
    
    z.parent=y
    if not y:
      self.root=z
    else:
      if z.key < y.key:
        y.left=z
      else:
        y.right=z
    
    self.size += 1

  def __delete_fixup(self, x):
    while x != self.root and x.color==Node.B:
      if x==x.parent.left:
        w=x.parent.right
        if w.color==Node.R:
          w.color=Node.B
          x.parent.color=Node.R
          self.__left_rotate(x.parent)
          w=x.parent.right
        if w.left.color==Node.B and w.right.color==Node.B:
          w.color=Node.R
          x=x.parent
        else:
          if w.right.color==Node.B:
            w.left.color=Node.B
            w.color=Node.R
            self.__right_rotate(w)
            w=x.parent.right
          w.color=x.parent.color
          x.parent.color=Node.B
          w.right.color=Node.B
          self.__left_rotate(x.parent)
          x=self.root
      else:
        w=x.parent.left
        if w.color==Node.R:
          w.color=Node.B
          x.parent.color=Node.R
          self.__right_rotate(x.parent)
          w=x.parent.left
        if w.right.color==Node.B and w.left.color==Node.B:
          w.color=Node.R
          x=x.parent
        else:
          if w.left.color==Node.B:
            w.right.color=Node.B
            w.color=Node.R
            self.__left_rotate(w)
            w=x.parent.left
          w.color=x.parent.color
          x.parent.color=Node.B
          w.left.color=Node.B
          self.__right_rotate(x.parent)
          x=root
    x.color=Node.B

import time
import sys
t1=time.clock()
f=open('in21_7.txt', 'r')  
l=f.readline().split()
s=[]
for i in l:
    s.append(int(i))
    
if __name__=="__main__":
  tree=RedBlackTree()
  for j in range(len(s)):
    tree.add(s[j])
z=str(tree)
tree.remove(10)
q=str(tree)   
t2=time.clock()
t=t2-t1
y=str(t)
ww=sys.getsizeof(t1)+sys.getsizeof(t2)+sys.getsizeof(s)+sys.getsizeof(tree)+sys.getsizeof(j)+sys.getsizeof(i)+sys.getsizeof(z)+sys.getsizeof(t)+sys.getsizeof(l)
memory=str(ww+sys.getsizeof(ww))
out=open("out_17_sec21_7.txt","w")
out.write("\nThe tree is "+z)
out.write("\nThe tree after deletion is "+q)
out.write("\nTime taken by program is "+y)
out.write("\nMemory used by program is "+memory+" bytes")
out.close()