package require TclOO

oo::class create Node {
     variable x
     variable y
     variable left
     variable right

     constructor {_x} {
          set x $_x
          set y [expr {int(rand()*2**31)}]
          set left {}
          set right {}
     }

     method get {var} {
          return [set $var]
     }

     method left {val} {
          set left $val
     }

     method right {val} {
          set right $val
     }
}

proc merge {lower greater} {
     if {$greater eq {} || $lower eq {}} {return [concat $lower $greater]}

     if {[$lower get y] > [$greater get y]} {
          $lower right [merge [$lower get right] $greater]
          return $lower
     } else {
          $greater left [merge $lower [$greater get left]]
          return $greater
     }
}

proc splitBinary {orig value} {
     if {$orig eq {}} {
          return {{} {}}
     }

     if {[$orig get x] < $value} {
          set splitPair [splitBinary [$orig get right] $value]
          $orig right [lindex $splitPair 0]
          return [list $orig [lindex $splitPair 1]]
     } else {
          set splitPair [splitBinary [$orig get left] $value]
          $orig left [lindex $splitPair 1]
          return [list $orig [lindex $splitPair 0]]
     }
}

proc merge3 {lower equal greater} {
     return [merge [merge $lower $equal] $greater]
}

oo::class create SplitResult {
     variable lower
     variable equal
     variable greater

     constructor {args}  {
          lassign $args lower equal greater
     }

     method unknown {args} {
          lassign $args var val
          if {[llength $args] == 1} {return [set $var]}
          return [set $var $val]
     }
}

proc tsplit {orig value} {
     lassign [splitBinary $orig $value] lower equalGreater
     lassign [splitBinary $equalGreater [expr {$value + 1}]] equal greater
     return [SplitResult new $lower $equal $greater]
}

oo::class create Tree {
     variable root

     constructor {} {
          set root {}
     }

     method has_value {x} {
          set splited [tsplit $root $x]
          set res [expr {[$splited equal] ne {}}]
          set root [merge3 [$splited lower] [$splited equal] [$splited greater]]
          return $res
     }

     method insert {x} {
          set splited [tsplit $root $x]
          if {[$splited equal] eq {}} {
               $splited equal [Node new $x]
          }
          set root [merge3 [$splited lower] [$splited equal] [$splited greater]]
     }

     method erase {x} {
          set splited [tsplit $root $x]
          set root [merge [$splited lower] [$splited greater]]
     }
}

set tree [Tree new]
set cur 5
set res 0

for {set i 1} {$i < 1000000} {incr i} {
     set a [expr {$i % 3}]
     set cur [expr {($cur * 57 + 43) % 10007}]
     switch $a {
          0 {
               $tree insert $cur
          }
          1 {
               $tree erase $cur
          }
          2 {
               if {[$tree has_value $cur]} {
                    incr res
               }
          }
     }
}
puts $res