You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.

Example 1:

Input: [1,2,3,3,4,5]

Output: True

Explanation:

You can split them into two consecutive subsequences :

1, 2, 3

3, 4, 5

Example 2:

Input: [1,2,3,3,4,4,5,5]

Output: True

Explanation:

You can split them into two consecutive subsequences :

1, 2, 3, 4, 5

3, 4, 5

Example 3:

Input: [1,2,3,4,4,5]

Output: False

Note:

1. The length of the input is in range of [1, 10000]

class Solution {

public:

    bool isPossible(vector<int>& nums) {

        int pre = nums[0] - 1;

        int a1 = 0, a2 = 0, a3 = 0;

        for (int i = 0; i < nums.size(); ) {

            int j = i;

            while (j+1 < nums.size() && nums[j+1] == nums[j]) ++j;

            int cnt = j - i + 1;

            int cur = nums[i];

            if (cur != pre + 1) {

                if (a1 != 0 || a2 != 0) return false;

                a3 = 0;

                a1 += cnt;

            } else {

                int b1 = 0, b2 = 0, b3 = 0;

                if (a1 > cnt) return false;

                b2 += a1, cnt -= a1, a1 = 0;

                if (a2 > cnt) return false;

                b3 += a2, cnt -= a2, a2 = 0;

                b3 += min(a3, cnt), cnt -= min(cnt, a3);

                a1 = cnt;

                a2 = b2;

                a3 = b3;

            }

            pre = cur;

            i = j + 1;

        }

        return a1 == 0 && a2 == 0;

    }

};

class Solution {

    public boolean isPossible(int[] nums) {

        int pre = Integer.MIN_VALUE, p1 = 0, p2 = 0, p3 = 0;

        int cur = 0, cnt = 0, c1 = 0, c2 = 0, c3 = 0;

        for (int i = 0; i < nums.length; pre = cur, p1 = c1, p2 = c2, p3 = c3) {

            for (cur = nums[i], cnt = 0; i < nums.length && cur == nums[i]; cnt++, i++);

            if (cur != pre + 1) {

                if (p1 != 0 || p2 != 0) return false;

                c1 = cnt; c2 = 0; c3 = 0;

            } else {

                if (cnt < p1 + p2) return false;

                c1 = Math.max(0, cnt - (p1 + p2 + p3));

                c2 = p1;

                c3 = p2 + Math.min(p3, cnt - (p1 + p2));

            }

        }

        return (p1 == 0 && p2 == 0);

    }

}