Simply Sitting on Chairs

Key Observation

If you sit on chair $i$, you mark chair $p_i$.

If $p_i\le i$, that mark is harmless: the chair is already visited, or it is the current chair after you stand up. No future disaster.

If $p_i>i$, then chair $p_i$ becomes a trap. When you reach it, the game ends immediately. So sitting at $i$ forbids you from safely visiting every chair in the open interval:

$$(i, p_i).$$

Those are the chairs where this decision is “active danger”. Cute little interval problem hiding inside a chair problem. Classic Codeforces nonsense, but friendly nonsense.

Fix the First Marked Chair

Assume the game first ends at chair $r$.

Then we may sit only on chairs $i<r$. For such an $i$, sitting is valid if it does not mark a chair strictly between $i$ and $r$; otherwise the game would have ended earlier.

So chair $i<r$ is usable iff:

$$p_i\le i \quad \text{or} \quad p_i\ge r.$$

Equivalently, it is unusable iff:

$$i<p_i<r.$$

Therefore, for a fixed $r$, the best number of chairs we can sit on before reaching $r$ is:

$$(r-1)-\#\{i<r \mid i<p_i<r\}.$$

But there is one more condition: chair $r$ must actually be marked before we get there. Since $p$ is a permutation, there is exactly one index $pos[r]$ such that:

$$p_{pos[r]}=r.$$

Thus $r$ can be the stopping chair iff:

$$pos[r]<r.$$

If that holds, our formula includes $i=pos[r]$, because $p_i=r\ge r$, so we can sit there and mark $r$.

Sweeping the Dangerous Intervals

For every $i$ with $p_i>i$, create interval $(i,p_i)$. While sweeping $r=1,2,\dots,n$, maintain:

$$bad(r)=\#\{i \mid i<r<p_i\}.$$

These are exactly the earlier chairs that we cannot sit on if we want to reach $r$.

Then for every valid stopping chair $r$ with $pos[r]<r$, candidate answer is:

$$r-1-bad(r).$$

We can maintain $bad$ with a difference array:

• interval $(i,p_i)$ contributes $+1$ to every integer $r$ with $i+1\le r\le p_i-1$;
• so do diff[i+1]++ and diff[p_i]--.

What If We Never Stop?

If we visit all chairs, then every chair we sit on must satisfy:

$$p_i\le i,$$

because any $p_i>i$ would mark a future chair and eventually kill the run.

So another candidate is:

$$\#\{i \mid p_i\le i\}.$$

This also covers boring cases like $n=1$, where the answer is $1$ if $p_1=1$.

Correctness Proof

We prove the algorithm returns the maximum possible number of chairs sat on.

First, consider any strategy that ends for the first time at chair $r$. It can only sit on chairs $i<r$. If it sat on some $i$ with $i<p_i<r$, then chair $p_i$ would have been marked before reaching it, so the game would have ended at $p_i$, earlier than $r`. Contradiction. Hence every sat chair is counted by:

$$(r-1)-\#\{i<r\mid i<p_i<r\}.$$

Also, for the game to end at $r$, some earlier chair must mark $r$. Since $p$ is a permutation, this is possible exactly when $pos[r]<r$. So no strategy ending at $r$ can beat our candidate for $r$.

Now suppose $pos[r]<r$. Sit on every chair $i<r$ such that $p_i\le i$ or $p_i\ge r$, and skip all chairs with $i<p_i<r$. Before reaching $r$, none of the sat chairs marks a chair in $[1,r-1]$ that has not already been visited. Also, chair $pos[r]$ is included and marks $r$. Therefore the game indeed reaches chairs $1,2,\dots,r-1$, sits exactly the candidate number of times, and stops at $r$. So the candidate is achievable.

Finally, if a strategy never stops, it cannot sit on any $i$ with $p_i>i$, because that would mark a future chair eventually visited later. Conversely, sitting on all $i$ with $p_i\le i$ never causes a future stop. Thus the all-visited candidate is exactly optimal among non-stopping strategies.

Taking the maximum over all stopping and non-stopping possibilities gives the global optimum.

Complexity

The sweep and difference array are linear:

$$O(n)$$

per test case, and the total input size is bounded by $2\cdot 10^5$, so this easily fits. Memory usage is:

$$O(n).$$