Let the stick lengths be $$$X, Y, Z$$$. The broken stick $$$X$$$ either forms two parallel sides or two perpendicular sides. In the first case, $$$X$$$ is even and $$$Y == Z$$$. In the second case, $$$X == Y+Z$$$. We try all choices of $$$X$$$.
Say we dislike $$$L$$$ songs — those $$$L$$$ songs must have unique ratings $$$q_i$$$ from $$$1$$$ to $$$L$$$. To minimize the sum of $$$|p_i - q_i|$$$, we should keep $$$q_i$$$ in the same order as $$$p_i$$$.
Optimal strategies can be described by $$$(x, k)$$$: decrease the lowest value by $$$x$$$, then set the largest $$$k$$$ values to the lowest value.
Let $$$M$$$ be the lowest value. For each $$$k = A[..i]$$$, let's find the least $$$x$$$ that we need. For $$$k = 0$$$, it is just $$$\max(0, \text{sum}(A) - K)$$$. For other $$$k$$$'s, we have the equation $$$(M-x) * (i+2) + \text{sum}(A[i+1 : -1]) \leq K$$$ which can be solved.
We try to classify all valid strings into disjoint sets to count them. Let $$$X_i$$$ be the set of all valid strings $$$t$$$ where $$$i$$$ is the last position where $$$s[i]$$$ and $$$t[i]$$$ differ. The answer is $$$1 + \sum_i X_i$$$.
To count $$$X_j$$$, let $$$i$$$ be the lowest index so that $$$s[i..j]$$$ contains $$$k$$$ ones. If this exists, then we either have $$$j-i$$$ spaces to fit $$$k$$$ or $$$k-1$$$ ones depending on the value of $$$s[j]$$$ (it must change).
First, $$$r_i = \sum_j s_{i,j} p_j$$$.
Now, observe $$$|x| = \max(x, -x)$$$, and $$$|x| + |y| = \max(x + y, x - y, -x + y, -x - y)$$$, etc. Using this idea, we can find the maximum surprise as the max over all $$$2^n$$$ possibilities of replacing $$$|x_i - r_i|$$$ with $$$x - r$$$ or $$$r - x$$$. This results in a sum of the form $$$c_0 + c_1 * p_1 + \cdots + c_n * p_n$$$, for which the best permutation can be chosen greedily (by the rearrangement inequality.)
Brute forcing small values, it seems we remove at most 3 values, so let's focus on removals.
Represent every prime as a random bitmask $$$\text{mask}(P)$$$. Then with $$$\text{mask}(X * Y) = \text{mask}(X) \oplus \text{mask}(Y)$$$, we can check whether a number is probably a square with $$$\text{mask}(X) = 0$$$.
Now we can use this trivially to solve for any $$$n$$$ with $$$\leq 2$$$ removals. For the others, try removing $$$n$$$ then applying the procedure again — we can check that this works, so every answer has $$$\leq 3$$$ removals and we've found the optimal answer for all $$$n$$$.
