100分排序栈的代码

100分求一个排序栈的代码
这个排序栈包含5个功能：
1，POP 
2,PUSH
3,取得栈中元素的最大值
4，取得栈中元素的最小值
5，取得栈中元素中值排在中间的元素的值

要求上面五个方法时间复杂度相同，且速度越快越好。

我能想到的最好的办法是 3，4，5为o(1),POP PUSH为 o（N），但是题目要5个复杂度相同，我预计最好的方法是5个都是logn。




[解决办法]
都为logn显然不是答案，logn做法太直接

直接一个普通的栈＋一个平衡树(比如sbt)
[解决办法]
栈中除了存一个栈顺序数组,还存一个值索引.
复杂度pop,push o(log2n), max, min, middle o(1)
[解决办法]