Find the First Value Repeated During a Left-to-Right Scan

Scan an integer array from left to right and return the first value encountered for a second time. If no value repeats, return `-1`. Implement `first_duplicate(values: int[]) -> int`. The answer is determined by the earliest second occurrence, not the smallest repeated value or the repeated value with the earliest first occurrence. ### Constraints & Assumptions - The array has at most 200,000 elements, each a signed 32-bit integer. - `-1` is also a valid element; the required return convention may therefore use the same value for a repeated `-1` and for no duplicate. - Do not reorder the input for the primary task, because scanning order determines the answer. ### Examples - `[2, 1, 3, 1, 2]` returns `1`; its second occurrence appears before the second `2`. - `[4, 7, 9]` returns `-1`. After explaining the primary algorithm and its time/space costs, discuss both reported variants: how the method changes when the input is already sorted, and how to solve the task if built-in set-like containers are unavailable. State the data-range or custom-structure assumptions of the latter approach. ```hint Record what the scan has already seen At each position, determine whether this exact value appeared in the prefix. Once that condition is true, later positions cannot produce an earlier second occurrence. ```