i used redblack tree on python and using a quick input using stdin
i passed test 8 time limit and met evening at 11

ok, it was a perpendicular but what about 15 test