# make a global red black tree
# add nodes in it
# RED => 0
# BLACK => 1
class RBNode:
"""docstring for RedBlack"""
def __init__ ( self , data= None , color= 0 , parent= None , leftChild= None , rightChild= None ) :
self .data = data
self .parent = parent
self .leftChild = leftChild
self .color = color
self .rightChild = rightChild
class RBTree:
"""insert rotate left , rotate right, fixup"""
def __init__ ( self ) :
self .root = RBNode( )
def insert( self , x) :
if self .root == None :
self .root = x
y = self .root
z= None
while y!= None :
z = y
if x.data > y.data :
y= y.rightChild
else :
y= y.leftChild
x.parent = z
if x.data > z.data :
z.rightChild = x
else :
z.leftChild = x #Rename this
def rotateLeft ( self , x) :
y = x.rightChild
x.rightChild = y.leftChild
if y.leftChild != None :
y.leftChild .parent = x
y.parent = x.parent
if x.parent == None :
self .root = y
elif x.parent .leftChild == x:
x.parent .leftChild = y
else :
x.parent .rightChild = y
y.leftChild = x
x.parent = y
#compltete!!
def rotateRight( self , x) :
y= x.leftChild
x.leftChild = y.rightChild
if x.leftChild != None :
x.leftChild .parent = x
y.parent = x.parent
if x.parent == None :
self .root = y
elif x == x.parent .leftChild :
x.parent .leftChild = y
else :
x.parent .rightChild = y
y.rightChild = x
x.parent = y
#compltete it
def insertFix( self , z) :
#CASE 1 parent of z is left child
# 1. uncle of z is red
if z.parent == None :
z.color = 1
return z
while z.parent .color == 0 :
if z.parent == z.parent .parent .leftChild : # parent of z if left child
y= z.parent .parent .rightChild # y uncle of z
if y.color == 0 :# and statement
z.parent .color = 1
y.color = 1
z.parent .parent .color = 0
z = z.parent .parent
else :
# 2. z is right child of its parent or uncle is black
if z == z.parent .rightChild :
z= z.parent
self .rotateLeft ( z)
#case
self .rotateRight ( z.parent .parent )
z.parent .color = 1
z.parent .parent .color = 0
else :#parent is right child
#uncle is red
if z.parent .parent .leftChild != None and z.parent .parent .color == 0 :
z.parent .parent .color = 0
z.parent .parent .leftChild .color = 1
z.parent .color = 1
z = z.parent .parent
else :
if z == z.parent .leftChild :
self .rotateRight ( z.parent )
self .rotateLeft ( z.parent .parent )
z.parent .color = 1
z.parent .leftChild .color = 0
z= z.parent
def Visit( x) :
if x!= None :
Visit( x.leftChild )
print ( x)
Visit( x.rightChild )
########### MAIN PROGRAMM #################
tree = RBTree( )
n = input ( )
p = raw_input ( ) .split ( )
for i in range ( 0 , n) :
node = RBNode( p[ i] )
tree.insert ( node)
tree.insertFix ( node)
IyBtYWtlIGEgZ2xvYmFsIHJlZCBibGFjayB0cmVlIAojIGFkZCBub2RlcyBpbiBpdAojIFJFRCA9PiAwCiMgQkxBQ0sgPT4gMQoKY2xhc3MgUkJOb2RlOgoJIiIiZG9jc3RyaW5nIGZvciBSZWRCbGFjayIiIgoJZGVmIF9faW5pdF9fKHNlbGYsZGF0YT1Ob25lLGNvbG9yPTAscGFyZW50PU5vbmUsbGVmdENoaWxkPU5vbmUscmlnaHRDaGlsZD1Ob25lKToKCQlzZWxmLmRhdGE9ZGF0YQoJCXNlbGYucGFyZW50PXBhcmVudAoJCXNlbGYubGVmdENoaWxkPWxlZnRDaGlsZAoJCXNlbGYuY29sb3I9Y29sb3IKCQlzZWxmLnJpZ2h0Q2hpbGQ9cmlnaHRDaGlsZAoKCgpjbGFzcyBSQlRyZWU6CgkJCSIiImluc2VydCByb3RhdGUgbGVmdCAsIHJvdGF0ZSByaWdodCwgZml4dXAiIiIKCQkJCgkJCQoJCQlkZWYgX19pbml0X18oc2VsZik6CgkJCQlzZWxmLnJvb3QgPSBSQk5vZGUoKQoKCQkJZGVmIGluc2VydChzZWxmLHgpOgoJCQkJaWYgc2VsZi5yb290PT1Ob25lOgoJCQkJCXNlbGYucm9vdCA9IHgKCQkJCXkgPSBzZWxmLnJvb3QKCQkJCXo9IE5vbmUKCQkJCXdoaWxlIHkhPU5vbmU6CgkJCQkJeiA9IHkKCQkJCQlpZiB4LmRhdGEgPiB5LmRhdGEgOgoJCQkJCQl5PXkucmlnaHRDaGlsZAoJCQkJCWVsc2U6CgkJCQkJCXk9eS5sZWZ0Q2hpbGQKCQkJCXgucGFyZW50ID0gegoJCQkJaWYgeC5kYXRhID4gei5kYXRhOgoJCQkJCXoucmlnaHRDaGlsZCA9IHgKCgkJCQllbHNlOgoJCQkJCXoubGVmdENoaWxkID0geCAjUmVuYW1lIHRoaXMgCQkKCgkJCWRlZiByb3RhdGVMZWZ0IChzZWxmLHgpOgoJCQkJeSA9IHgucmlnaHRDaGlsZAoJCQkJeC5yaWdodENoaWxkID0geS5sZWZ0Q2hpbGQKCQkJCWlmIHkubGVmdENoaWxkICE9IE5vbmU6CgkJCQkJeS5sZWZ0Q2hpbGQucGFyZW50ID0geAoJCQkJeS5wYXJlbnQ9IHgucGFyZW50CgkJCQlpZiB4LnBhcmVudCA9PSBOb25lOgoJCQkJCXNlbGYucm9vdCA9IHkKCQkJCWVsaWYgeC5wYXJlbnQubGVmdENoaWxkID09eDoKCQkJCQl4LnBhcmVudC5sZWZ0Q2hpbGQ9eQoJCQkJZWxzZToKCQkJCQl4LnBhcmVudC5yaWdodENoaWxkID0geQoJCQkJeS5sZWZ0Q2hpbGQgPSB4CgkJCQl4LnBhcmVudD15CgoJCQkJI2NvbXBsdGV0ZSEhCgoJCQlkZWYgcm90YXRlUmlnaHQoc2VsZix4KToKCQkJCXk9IHgubGVmdENoaWxkCgkJCQl4LmxlZnRDaGlsZCA9IHkucmlnaHRDaGlsZAoJCQkJaWYgeC5sZWZ0Q2hpbGQgIT1Ob25lIDoKCQkJCQl4LmxlZnRDaGlsZC5wYXJlbnQgPSB4CgoJCQkJeS5wYXJlbnQgPSAgeC5wYXJlbnQKCQkJCWlmIHgucGFyZW50ID09IE5vbmU6CgkJCQkJc2VsZi5yb290ID0geQoJCQkJZWxpZiB4ID09IHgucGFyZW50LmxlZnRDaGlsZDoKCQkJCQl4LnBhcmVudC5sZWZ0Q2hpbGQgPSB5CgkJCQllbHNlOgoJCQkJCXgucGFyZW50LnJpZ2h0Q2hpbGQgPSB5CgoJCQkJeS5yaWdodENoaWxkID14CgkJCQl4LnBhcmVudCA9IHkKCQkJCSNjb21wbHRldGUgaXQKCgkJCWRlZiBpbnNlcnRGaXgoc2VsZix6KToKCQkJCSNDQVNFIDEgcGFyZW50IG9mIHogaXMgbGVmdCBjaGlsZAoJCQkJIyAxLiB1bmNsZSBvZiB6IGlzIHJlZCAKCQkJCWlmIHoucGFyZW50ID09IE5vbmU6CgkJCQkJei5jb2xvcj0xCgkJCQkJcmV0dXJuIHoKCgkJCQl3aGlsZSB6LnBhcmVudC5jb2xvciA9PSAwOgoJCQkJCWlmIHoucGFyZW50ID09IHoucGFyZW50LnBhcmVudC5sZWZ0Q2hpbGQ6ICAjIHBhcmVudCBvZiB6IGlmIGxlZnQgY2hpbGQKCQkJCQkJeT0gei5wYXJlbnQucGFyZW50LnJpZ2h0Q2hpbGQgICAgICMgeSB1bmNsZSBvZiB6CgkJCQkJCWlmIHkuY29sb3IgPT0gMDojIGFuZCBzdGF0ZW1lbnQKCQkJCQkJCXoucGFyZW50LmNvbG9yID0gMQoJCQkJCQkJeS5jb2xvciA9IDEKCQkJCQkJCXoucGFyZW50LnBhcmVudC5jb2xvciA9IDAKCQkJCQkJCXogPSB6LnBhcmVudC5wYXJlbnQKCQkJCQkJZWxzZToKCQkJCQkJCSMgMi4geiBpcyByaWdodCBjaGlsZCBvZiBpdHMgcGFyZW50IG9yIHVuY2xlIGlzIGJsYWNrCgkJCQkJCQlpZiB6ID09IHoucGFyZW50LnJpZ2h0Q2hpbGQ6CgkJCQkJCQkJej0gei5wYXJlbnQKCQkJCQkJCQlzZWxmLnJvdGF0ZUxlZnQoeikKCQkJCQkJCQkKCQkJCQkJCQoJCQkJCQkJCSNjYXNlCgkJCQkJCSAJc2VsZi5yb3RhdGVSaWdodCh6LnBhcmVudC5wYXJlbnQpCgkJCQkJCSAJei5wYXJlbnQuY29sb3IgPTEKCQkJCQkJCXoucGFyZW50LnBhcmVudC5jb2xvciA9IDAKCgkJCQkJZWxzZSA6I3BhcmVudCBpcyByaWdodCBjaGlsZCAKCQkJCQkJI3VuY2xlIGlzIHJlZCAKCQkJCQkJaWYgei5wYXJlbnQucGFyZW50LmxlZnRDaGlsZCE9Tm9uZSBhbmQgei5wYXJlbnQucGFyZW50LmNvbG9yPT0wOgoJCQkJCQkJei5wYXJlbnQucGFyZW50LmNvbG9yID0gMAoJCQkJCQkJei5wYXJlbnQucGFyZW50LmxlZnRDaGlsZC5jb2xvciA9IDEKCQkJCQkJCXoucGFyZW50LmNvbG9yID0gMQoJCQkJCQkJeiA9IHoucGFyZW50LnBhcmVudAoJCQkJCQllbHNlOgoJCQkJCQkJaWYgeiA9PSB6LnBhcmVudC5sZWZ0Q2hpbGQ6CgkJCQkJCQkJc2VsZi5yb3RhdGVSaWdodCh6LnBhcmVudCkKCQkJCQkJCXNlbGYucm90YXRlTGVmdCh6LnBhcmVudC5wYXJlbnQpCgkJCQkJCQl6LnBhcmVudC5jb2xvciA9IDEKCQkJCQkJCXoucGFyZW50LmxlZnRDaGlsZC5jb2xvciA9IDAKCQkJCQkJCXo9ICB6LnBhcmVudAoJCQkJCgoKZGVmIFZpc2l0KHgpOgoJaWYgeCE9IE5vbmU6CgkJVmlzaXQoeC5sZWZ0Q2hpbGQpCgkJcHJpbnQoeCkKCQlWaXNpdCh4LnJpZ2h0Q2hpbGQpCgoKCgojIyMjIyMjIyMjIyBNQUlOIFBST0dSQU1NICMjIyMjIyMjIyMjIyMjIyMjCgp0cmVlID0gUkJUcmVlKCkKbiA9IGlucHV0KCkKcCA9IHJhd19pbnB1dCgpLnNwbGl0KCkKCmZvciBpIGluIHJhbmdlKDAsbik6Cglub2RlID0gUkJOb2RlKHBbaV0pCgl0cmVlLmluc2VydChub2RlKQoJdHJlZS5pbnNlcnRGaXgobm9kZSkKCQoKCgoKCgoKCg==