array median transformation using the min number of steps
In the comments, Wu Yin claimed an upper bound of $\lceil \log_2 n \rceil$, although I think this is only true if the position of the maximum is known. In fact, consider the following argument. Assume $A$ is filled with $N-1$ ones and one maximal element $\max$. Any first step on a subarray $A[x,y]$ of more than 2 elements will necessarily set the subarray to all $1$'s. In particular, if we don't know the position of $\max$, we can only apply a step to subarrays of length 2, or otherwise we run the risk of "destroying" our maximum element. Hence, without knowing the position of our maximimal element, we can only probe the array by consecutively applying the operation to $A[i,i+1]$ for all $i$. This will necessarily create a subarray of length 2 that is filled with $\max$. Recurring leads to a linear time algorithm, which I think is optimal.

Algorithm:

Let $step(x,y)$ denote an operation on the subarray $A[x,y]$ as is defined in the question.


Perform $step(i,i+1)$ for all $0\leq i &lt; N$. After that, there is some 2-length subarray containing only $\max$.
Perform $step(i,i+3)$ for all $0\leq i &lt; N-3$. After that, there is some 4-length subarray filled with $\max$.
Generally, we double in each such iteration the array size in each step. After that, the original array $A$ contains only $\max$.


Running Time:

In the first iteration, we perform $N/2$ steps, in the subsequent one, $N/4$, then $N/8$, etc. The sum over all this is smaller than $N$. I think this is optimal, since without looking at all elements (or at least $N/2$ elements), we don't know where $\max$ is, and can not use any step on any subarray larger than $2$.