class Solution {
public:
    bool isPossible(vector<int>& nums) {
        int len = nums.size(), i = 0, prev = -1;
        //dp[i][1]/dp[i][2] represents number of consecutive subsequences with length 1/2 ending at i
        //dp[i][3] represents number of consecutive subsequences with length >= 3 ending at i
        vector<vector<int>> dp;
        while(i < len)
        {
            int num = nums[i], count = 0;
            while(i < len && nums[i] == num)
            {
                ++i;
                ++count;
            }
            if(dp.empty() || num != prev + 1)
            {
                if(dp.size() && (dp.back()[1] != 0 || dp.back()[2] != 0 || dp.back()[3] <= 0))
                    return false;
                vector<int> seq(4, 0);
                seq[1] = count;
                seq[2] = 0;
                seq[3] = 0;
                dp.push_back(seq);
            }
            else
            {
                int p1 = dp.back()[1], p2 = dp.back()[2], p3 = dp.back()[3];
                //there is sequence with length 1/2 that we cannot fill
                if(count < p1 + p2)
                    return false;
                
                vector<int> seq(4, 0);
                seq[2] = p1;
                seq[3] = min(count - p1, p2 + p3);
                seq[1] = max(0, count - (p1 + p2 + p3));
                dp.push_back(seq);     
            }
            prev = num;
        }
        return dp.back()[1] == 0 && dp.back()[2] == 0 && dp.back()[3] > 0;
    }
};