Too Far For Comfort

*This is the hard version of TOOFAREZ, and is worth $60$ points. Note that the input formats of both problems differ slightly - in particular, this version has an additional array $A$ as input.* An array $A$ of length $M$ is said to be *prefix-balanced* under the following conditions: - Let $S_A$ denote the set of all elements that appear in $A$. - For each $x \in S_A$, and index $i$ ($1 \leq i \