1946. An Iterator That Never Repeats Itself

A source hands out n values in order, and may hand out the same value more than once. Wrap it so that a value is returned at most once ever: the second and later copies are skipped as though they were not there.

next print the next value never returned before, and consume it peek print that value without consuming it distinct print how many values have been returned so far hasnext print yes or no

next and peek print done when no unreturned value remains.

``` values 1 1 2 1 3 3

next -> 1 next -> 2 the second 1 is skipped distinct -> 2 next -> 3 the third 1 is skipped as well peek -> done both 3s are now accounted for hasnext -> no ```

## This is not the empty-group skip

Problem 1941 skips an EMPTY GROUP, which is a structural property: you can see from the input whether a group is empty. Here the skip depends on CONTENT and on history: whether a value must be skipped depends on everything returned before it, which no amount of looking at the current position reveals. That is why this needs a set and that one needed only a loop.

## What most people try first

Skip one duplicate. The code reads if the next value has been returned, advance past it, which is right exactly when duplicates never occur twice in a row. The input 1 1 1 2 breaks it immediately: the first next returns 1, the second skips one copy and then returns the third 1, so a value is returned twice and the whole contract is broken.

The second attempt deduplicates the input up front and then walks the result. That is correct, and worth knowing, because it is the implementation that the answers can be checked against. It costs O(n) memory beyond the stream and it answers distinct as a cursor position rather than a count.

## A cursor, a set, and a skip loop

``` at position in the source seen the values already returned

advance: while at < n and values[at] is in seen: at += 1

next: advance; if at = n -> done otherwise print values[at], add it to seen, at += 1 peek: advance; values[at], or done hasnext: advance; whether at < n distinct: the size of seen ```

The skip is a while, not an if, because any number of copies may sit next to each other. Running advance before hasnext and peek as well as before next is what makes those two agree with each other: without it, hasnext could say yes while the only remaining values are all duplicates.

## Why it is correct

Two invariants. Every value in seen has been returned exactly once, because the only place that adds to seen is the same statement that prints. And after advance, either at = n or values[at] is not in seen, so the value about to be returned has never been returned. Together those give the contract: no value is ever returned twice, and no value that has never been returned is skipped.

The cost argument is amortised. A single next may skip a long run of duplicates, but at only moves forwards and never exceeds n, so the total skipping work across the entire program is O(n) however it clusters.

## The boundary that breaks a careless implementation

A peek that records the value as returned. The very next next then skips past the value the peek promised, which is the one bug in this problem that makes two operations contradict each other rather than making one of them wrong. peek must read seen and never write it.

The other case is a stream that is entirely one repeated value, where exactly one next succeeds and every later operation must report exhaustion even though the source has values left.

## Overflow

Values reach 1000000000, which fits in a signed 32 bit integer since the limit is 2147483647. They are used as set keys and printed, never summed, so nothing widens. The counts, both distinct and the cursor, reach 200000. Negative values are not allowed here, so no value can collide with a sentinel chosen below zero.

## Cost

O(1) expected per operation, amortised over the skipping, so O(n + q) for the run, with O(n) memory for the set. The judge cannot enforce the per-operation bound, so re-scanning the returned values on each step passes every declared test while costing about 4 * 10^10 comparisons at the stated limits.

Constraints - `0 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `0 ≤` each value `≤ 1000000000` - every operation runs in `O(1)` expected, amortised over the skipping - the judge cannot enforce that: the declared tests are small and there is no test generator yet, so rescanning the returned values on each step passes them while doing about `4 * 10^10` comparisons at the stated limits