at first i wrote bst,and i got tle at testcase 3.
Now i know that i should have written SBT such as treap.

<Chinese>闫X远，“SBT”是陈启峰大牛的“Size Balanced Tree”的专用简称，和Treap不是一码事。你大概是想说“平衡二叉树”吧？这个题用SBT, Treap,或者一种O(nlogn)的基于归并排序的算法都能AC。</Chinese>
lonelycorn, the word "SBT" is for Chen Qifeng's "Size Balanced Tree", which is different from Treap. I think you were saying "Balanced BST".

And yes, treap and SBT both work, and a simple algo.,O(nlogn) based on mergesort also works.

I've written AVL Tree in Java and AC in 0.7 sec. Be careful, this solution should work fast, or will get TLE!