def maxTree(self, A):
        """
        Cartesian Tree, Heap-ordered, treap, stack O(n)
        http://en.wikipedia.org/wiki/Cartesian_tree

        using stack
        1. construct left tree and maintain the Cartesian tree
        2. connect right tree
        O(n) since each node on the tree is pushed and popped out from stack once 


        :param A: Given an integer array with no duplicates.
        :return: The root of max tree.
        """
        stk = []
        for a in A:
            cur = TreeNode(a)
            while stk and cur.val <= stk[-1].val:
                pre = stk.pop()
                pre.right = cur.left
                cur.left = pre

            stk.append(cur)

        pre = None
        while stk:
            cur = stk.pop()
            cur.right = pre
            pre = cur

        return pre
dataset/ETHPy150Open algorhythms/LintCode/Max Tree.py/Solution.maxTree/swapped operands of `<=`