The key idea that wasn’t allowing me to come up with a good solution is the following: If you have an array $$A$$ which has leader $$x$$ (the leader is the unique element that occurs more than in half of the array), then for every separation of $$A$$ into $$A[0..i), A[i..n)$$, if they have the same leader, then the leader of both is $$x$$. This follows from noticing that if $$z$$ is a leader in $$A[0..i)$$, then it occurs more than $$\lceil \frac{i}{2} \rceil$$ elements, and similarly, if z is the leader of $$A[i..n)$$, then x occurs more than $$\lceil \frac{n-i}{2} \rceil$$. In total, if both slices have leader $$z$$, it must occur more than $$\lceil \frac{n}{2} \rceil$$, which means that $$y=x$$ as required.