Hints: Simply Sitting on Chairs

When you sit on chair $i$, you mark chair $p_i$. Reaching a marked chair ends the game entirely — you lose every chair after it, not just that one.

Split chairs into two categories based on $p_i$ vs $i$. What happens if $p_i \le i$ (the marked chair is at or before the current position)? What if $p_i > i$?

Answer to Hint 1: If $p_i \le i$, chair $p_i$ has already been visited (you visit chairs in order $1, 2, \ldots$). Marking an already-visited chair has no future consequence — it’s completely safe to sit.

If $p_i > i$, sitting marks a chair you haven’t reached yet. When you later arrive at that chair, the game ends immediately. So sitting on an “unsafe” chair risks cutting your game short.

Is it ever worth sitting on an unsafe chair?

Answer to Hint 2: No. Sitting on an unsafe chair ($p_i > i$) gives you $+1$ but marks some future chair $p_i$, which terminates the game when you reach it — costing you every remaining chair from $p_i$ onward. That’s always a net loss (or at best breaks even while adding risk).

So you should skip every unsafe chair and sit on every safe one. Does skipping all unsafe chairs guarantee that no future chair ever gets blocked?

Answer to Hint 3: Yes. If you never sit on an unsafe chair, you never mark any future chair. That means no chair is ever marked when you arrive at it, so the game never ends early. You visit all $n$ chairs and sit on every safe one without interference.

The answer is simply the number of indices $i$ (from $1$ to $n$) satisfying $p_i \le i$. This is computable in a single $O(n)$ pass while reading the input.