Editorial

Keeping Multiple Positions

Editorial

The possible original indices of the last remaining element are exactly $\lfloor N/2\rfloor+1$ through $N$ . Output the maximum $A_i$ in this range.

Compute this maximum while reading the sequence, using $O(N)$ time and $O(1)$ additional space.

Proof

Let $q$ be the product of all values of $k$ chosen so far, initially $1$ . The remaining elements always have original indices

q,2q,\ldots,\left\lfloor\frac{N}{q}\right\rfloor q.

⌊qN⌋

q

.

Keeping every $k$ -th element leaves exactly the multiples of $qk$ , preserving this property.

Exactly one element remains when $\lfloor N/q\rfloor=1$ , or equivalently,

\left\lfloor\frac{N}{2}\right\rfloor+1\leq q\leq N.

Conversely, any index $i$ in this range can be left alone by choosing $k=i$ in the first operation. If $N=1$ , no operation is needed.

Thus, precisely the elements in the stated range can remain last.