class Solution {
public:
    bool helper(vector<int>& preorder, int l, int r, int upper, int lower){
        if(preorder[l]>=upper||preorder[l]<=lower)
            return false;

        if(l==r)
            return true;

        int i;
        int p0=l+1, p1=r+1;
        while(p0<=p1&&p0<r+1){
            i = (p0+p1)/2;
            if(preorder[i]>=preorder[l]&&preorder[i-1]<=preorder[l])
                break;

            if(preorder[l]>preorder[i])
                p0=i+1;

            if(preorder[l]<preorder[i])
                p1=i-1;
        }
        i = (p0+p1)/2;

        bool left=true, right=true;
        if(i!=l+1)
            left = helper(preorder, l+1, i-1, preorder[l], lower);
        if(i<=r)
            right = helper(preorder, i, r, upper, preorder[l]);

        return left&&right;
    }

    bool verifyPreorder(vector<int>& preorder) {
        bool res=true;
        if(preorder.empty())
            return res;

        res=helper(preorder, 0, preorder.size()-1, INT_MAX, INT_MIN);

        return res;
    }
};