Hints: Antimedian Deletion

You may delete only the minimum or maximum of three consecutive elements. If the array has only one element, what can you do?

Answer to Hint 1: With length $n \lt 3$, no operation is possible, so the only reachable array is the whole array. For $n=1$, the minimum length containing $p_i$ is $1$.

For $n \ge 2$, try to guess the answer before designing a long construction. What is the smallest length that could ever remain when you keep deleting from triples?

Answer to Hint 2: After any deletion the length drops by $1$, so you cannot go below $2$ while still having any elements left. So if you can always reach length $2$ while keeping a chosen value, the answer for that index is $2$.

Why might length $2$ always be achievable when $n \ge 2$ for every element of a permutation?

Answer to Hint 3: Intuitively, you can repeatedly remove “extreme” elements elsewhere until only two numbers remain; the operation always lets you peel off a global min or max inside some window of three, so you are not forced to delete your marked element until the very end.

In fact, for this problem the answer turns out not to depend on the permutation at all when $n \ge 2$.

Answer to Hint 4: The minimum length containing $p_i$ is $1$ if $n=1$, and $2$ for every $i$ if $n \ge 2$. A full rigorous proof is optional for coding; implementing this closed form matches the intended solution.