All Lengths Subtraction

We need decide whether the permutation can be created by choosing one interval of every length and subtracting from it.

A much cleaner way to look at it: reverse time.

Instead of starting with $p$ and subtracting, start with all zeros and do the operations in reverse order:

• add $1$ to some subarray of length $n$,
• add $1$ to some subarray of length $n-1$,
• add $1$ to some subarray of length $n-2$,
• ...,
• add $1$ to some subarray of length $1$.

At the end, we want to get exactly $p$.

Key Shape Observation

The length-$n$ interval is forced: it is the whole array.

Now look at the length-$(n-1)$ interval. Any subarray of length $n-1$ is the whole array except either the left end or the right end.

Then a length-$(n-2)$ interval has removed two positions total from the outside. If the final values are a permutation, the construction that works is exactly this peeling process: each shorter interval is obtained by removing one current endpoint.

So the intervals form a nested chain:

$$[1,n] \supset \text{some interval of length } n-1 \supset \text{some interval of length } n-2 \supset \cdots$$

Each time, we delete either the current left endpoint or the current right endpoint.

Now ask: what final value does a deleted position get?

If a position is removed right after it has been included in exactly $x$ added intervals, then its final value is $x$. Once removed, it is never touched again.

Therefore:

• the position with value $1$ must be removed first, so it must be at one of the two ends;
• after removing it, the position with value $2$ must be at one of the new two ends;
• after removing that, value $3$ must be at one of the new ends;
• and so on.

This gives a dead-simple test.

Algorithm

Keep two pointers:

• $l$ at the left end,
• $r$ at the right end.

For every value $x$ from $1$ to $n$:

• if $p_l=x$, remove the left end: $l++$;
• else if $p_r=x$, remove the right end: $r--$;
• else $x$ is trapped inside, so answer NO.

If all values from $1$ to $n$ can be removed this way, answer YES.

Why This Is Correct

Suppose a valid sequence of operations exists. Reverse it. We are adding intervals of lengths $n,n-1,\dots,1$. The position with final value $1$ was included only in the length-$n$ interval, so it cannot be inside the length-$(n-1)$ interval. Since the length-$(n-1)$ interval skips only one endpoint, value $1$ must be at an endpoint.

After removing that endpoint from consideration, apply the same argument to value $2$: it must be excluded from the next smaller interval, so it must be an endpoint of the remaining segment.

Repeat this argument for every value. So any valid permutation must pass the two-pointer peeling test.

Conversely, if the peeling test passes, we can construct the intervals backwards. Start with the whole array, and whenever value $x$ is peeled from the left or right, choose the next smaller interval as the remaining segment. This creates one valid interval of each length, and each position receives exactly as many additions as its value. Reverse those additions, and we get a valid subtraction sequence.

So the two-pointer condition is both necessary and sufficient. No hidden DP, no wizardry, just peeling the array like it owes you money.

Complexity

Each element is checked and removed once.

$$O(n)$$

per test case, with $O(1)$ extra memory.