636. Keeping At Most Two of Each

A non-decreasing array is given. Remove extra copies so that no value appears more than TWICE. The values that remain keep their order.

Print how many values remain, and then those values.

1 1 1 2 2 3 -> 5 1 1 2 2 3 0 0 1 1 1 1 2 3 3 -> 7 0 0 1 1 2 3 3

## The rule, in one comparison

Problem 54 removes duplicates entirely, keeping one of each. This keeps two, and the change is smaller than it looks.

With a read pointer r and a write pointer w:

if w < 2 or a[r] != a[w-2]: a[w] = a[r]; w += 1

Keep the value when fewer than two have been written at all, or when it differs from the value written TWO places back.

## Why comparing against the output works

The check looks at a[w-2], a value already WRITTEN, not at the input. That is what makes it correct: the last two written values are exactly the last two kept, so if the incoming value differs from the one two back, at most one copy of it has been kept so far.

Comparing against the input instead, say a[r] != a[r-2], is wrong as soon as anything has been dropped, because r and w have drifted apart.

That is the whole lesson of this problem: when compacting in place, the decision is made against the OUTPUT written so far, not the input being read.

## Why sortedness matters

Equal values are adjacent, so "how many copies have I kept" is answered by looking a fixed distance back. On an unsorted array the same rule is meaningless and a count per value would be needed instead.

## Generalising

To keep at most k of each, compare against a[w-k] and start with w < k. The two-pointer skeleton does not change at all, which is a good sign that the right invariant was found.

## Boundaries

A single value is always kept. Every value distinct keeps everything.

## Cost

Time O(n). Space O(1) beyond the input.

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ each value ≤ 10^9` - the array is non-decreasing