Beautiful Permutation

The statement is interactive, but the hacked format gives the hidden permutation and the hidden segment in the input. So yes, the shortest accepted hacked solution can just read $l,r$ and print them. That feels illegal, but in the hacked version it is literally the data format.

Still, the actual intended idea is worth understanding, because it is clean and it explains why the tags say binary search.

Key Observation

The modification only adds $1$ to each index in the hidden interval. Therefore, for any range $[L,R]$:

$$\sum_{i=L}^{R} a_i - \sum_{i=L}^{R} p_i$$

is exactly the number of modified positions inside that range.

The values of the permutation cancel out. The permutation part is mostly there so the interactive queries have something to ask about. Sneaky, but not that sneaky.

Use Prefixes

Define:

$$d(x)=\sum_{i=1}^{x} a_i - \sum_{i=1}^{x} p_i$$

This counts how many changed positions are inside prefix $[1,x]$.

So:

• if $x<l$, then $d(x)=0$;
• if $l \le x \le r$, then $d(x)=x-l+1$;
• if $x>r$, then $d(x)=r-l+1$.

That means $d(x)$ is monotonic: flat at $0$, then rising, then flat again.

Finding the Endpoints

The left endpoint is the first prefix with a positive difference:

$$l=\min\{x:d(x)>0\}$$

The total length of the modified segment is:

$$d(n)=r-l+1$$

Then the right endpoint is the first prefix that has collected all modified positions:

$$r=\min\{x:d(x)=d(n)\}$$

Both are standard binary searches on monotonic predicates.

For the Hacked Version

The actual non-interactive input contains:

1. $n$
2. the permutation $p$
3. the hidden pair $l,r$

So there is nothing to discover. The accepted offline solution just reads the hidden pair and prints it. This is one of those interactive-to-hacks conversions where the “real” algorithm and the AC submitted code are not the same thing. The input format wins. Always.