1088. Dealing Into Runs of at Least Three

n cards are given in NON-DECREASING order of their numbers. Deal every card into runs of CONSECUTIVE numbers, where each run must be at least three cards long. A run is a sequence v, v+1, v+2, ... using one card of each value.

Print yes if it can be done, or no otherwise.

1 2 3 3 4 5 -> yes 1 2 3 | 3 4 5 1 2 3 3 4 4 5 5 6 -> yes 1 2 3 | 3 4 5 | 4 5 6 1 2 3 4 4 -> no 1 2 3 4 5 6 7 8 9 -> yes one run of nine, or three of three

## What most people try first

Backtracking over which run each card joins. The search space is huge and it is the brute force this problem was checked against on hands of at most a dozen cards.

Counting alone does not work either: 1 1 1 2 2 2 has six cards and no legal dealing, while 1 2 3 3 4 5 has six and does.

## Extend an existing run whenever you can

Walk the cards in increasing order. For each card v:

* if some run currently ENDS at v - 1, extend it to end at v * otherwise, start a new run at v, which requires a spare v+1 and a spare v+2 * if neither is possible, answer no

Two counters do the bookkeeping:

``` left[value] = cards of that value not yet used end[value] = how many runs currently end at that value

for each card v in order: if left[v] == 0: continue already consumed by an earlier step left[v] -= 1 if end[v-1] > 0: end[v-1] -= 1; end[v] += 1 else if left[v+1] > 0 and left[v+2] > 0: left[v+1] -= 1; left[v+2] -= 1; end[v+2] += 1 else: answer no answer yes ```

## Why extending beats starting

Suppose a legal dealing exists in which card v STARTS a new run while some other run R already ends at v - 1. Take the whole new run, v, v+1, ..., and append it to R instead. R ends at v - 1 and the appended part starts at v, so the join is consecutive, and the result is one longer run, which is still at least three cards. The new run disappears, so no run has become too short.

So extending is always at least as good, and the greedy never has to consider starting a run while an extension is available. That converts a search into a sweep.

## Why the new run must take exactly v+1 and v+2

A new run needs at least three cards, so it needs a v+1 and a v+2 at minimum. Taking exactly those two, rather than more, is right because anything longer can be obtained later by EXTENDING this run, which the sweep will do for free when it reaches v+3. Taking more now would only make the choice earlier without making it better.

## The counter that is easy to get wrong

end[v-1] and left[v+1] are different quantities. end counts runs waiting for their next card; left counts cards not yet placed. Using one array for both makes 1 2 3 3 4 5 fail, because the second 3 looks like it has already been consumed.

And the first line of the loop, skipping a card whose left is already zero, is needed because a card can be consumed by an earlier card's new-run step before the sweep reaches it.

## Overflow

Counts are bounded by n = 100000 and values by 10^9. Looking up v + 2 reaches 10^9 + 2, inside the signed 32 bit limit of 2147483647.

## Cost

Time O(n) with hash maps, or O(n log n) with ordered ones. Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ card ≤ 1000000000` - the cards are given in non-decreasing order