774. Split Array into Consecutive Subsequences

0

Medium

Given an array of integers, nums, that is sorted in non-decreasing order, determine if it is possible to split nums into one or more subsequences that meet the following conditions: each subsequence is a consecutive increasing sequence, and all subsequences have a length of 3 or more. Return true if it is possible to split nums according to these conditions, or false otherwise. A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements.

Input Format

The first argument is an integer, n, representing the number of elements in the array nums. The next n arguments are the elements of the array nums.

Output Format

The output should be either true or false.

Example

Input

6 1 2 3 3 4 5

Output

true

Constraints

1 <= nums.length <= 10^4
-1000 <= nums[i] <= 1000
nums is sorted in non-decreasing order.