1940. Adding a Peek to Something You Can Only Pull

A source hands out n values in order. The ONLY thing it can do is hand over the next one, which consumes it: there is no way to look without taking, and no way to put anything back. Build a wrapper around it with four operations:

next print the next value and consume it peek print the next value WITHOUT consuming it hasnext print yes or no calls print how many times the source has been pulled so far

n = 3, the source holds 7 8 9 peek -> 7 one pull was needed to see it calls -> 1 next -> 7 already held, so no pull calls -> 1 next -> 8 not held, so one pull calls -> 2 peek -> 9 next -> 9 next -> done calls -> 3

## The rules, stated so the answer is decidable

• Every operation prints exactly one line.
• The wrapper may hold back AT MOST ONE value. That is the whole design
• constraint, and the calls operation is what makes it observable: an
• implementation that pulls twice for one value prints a different number.
• peek pulls from the source only when it is not already holding a value, and
• only when the source has one to give. It then prints that value and keeps
• holding it.
• next prints the held value if there is one and stops holding it, pulling
• nothing. Otherwise it pulls one and prints that.
• hasnext never pulls. It prints yes when a value is held or the source has
• more, and no otherwise.
• next and peek print the word done when nothing is held and the source is
• exhausted. Neither changes anything in that case, including the pull count.
• calls counts pulls, not operations. Repeated peek calls with no next
• between them pull once in total.
• n may be 0, in which case the line of values is empty and every next and
• peek prints done from the start.

## What most people try first

Make peek pull a value, print it, and leave it consumed. That looks right for a single peek and destroys the stream: the value it reported is gone, so the following next returns the one after it. Every answer from then on is shifted by one, which is why the pull count is part of the output.

The second attempt makes peek pull every time, so three peek calls in a row consume three values. calls catches that one directly.

## One value of memory is enough

held the value being held back, or nothing exhausted whether the source has run out

A peek that is not already holding fills held. A next empties it. That is the entire structure, and it is the general technique: an interface that cannot look ahead gets a lookahead by reading one item early and remembering it.

## Why one value is enough, and why a second is not needed

peek must report the value that the next next will return. That value is either already held or is the source's next, so reading it once and holding it satisfies both operations. No operation ever needs the value AFTER that one, so nothing deeper has to be read, and reading deeper would break the pull count.

The done rule is what keeps the two cases apart. "Nothing held and the source exhausted" is the only state in which there is no next value, and it is different from "nothing held but the source has more", where a pull is needed. An implementation that tracks only exhaustion and forgets to check held reports done while still holding a value, which is the other common bug here.

## Cost

O(1) per operation, with memory for exactly one value.

## Overflow

Values reach 10^9, which fits in a signed 32 bit integer since the limit is 2147483647, and are never summed. The pull count reaches 2 * 10^5. Nothing here needs 64 bit arithmetic.

Constraints - `0 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `0 ≤` each value `≤ 1000000000` - the wrapper may hold back at most one value at a time - each of the four operations must run in `O(1)`, so the whole run is `O(q)` - the judge cannot enforce the holding rule directly, but the `calls` output does: the declared tests are small and there is no test generator yet, so the contract is enforced by making the pull count observable rather than by timing