class Solution {
public:
    vector<int> seq;
    bool verifySequenceOfBST(vector<int> sequence) {
        seq = sequence;
        return dfs(seq,0,seq.size() - 1);
    }

    bool dfs(vector<int> seq,int l,int r){
        if(l >= r) return true;
        int root = seq[r];
        int k = l;
        while(l < r && root > seq[k]) k++;
        for(;k < r;++k){
            if(seq[k] < root) return false;
        }

        return dfs(seq,l,k - 1) && dfs(seq,k,r - 1);
    }
};