Minimum cost to convert one array to another
Let distinct elements of $B$ be $b_1,b_2,\ldots$ where $b_1&gt;b_2&gt;\cdots$. There must be an optimal solution where it first sets a range to $k_1$ then set a range to $k_2$ and so on, such that $k_1\ge k_2\ge\cdots$ (otherwise one can swap related operations to meet the constraint without changing the result), and $k_1,k_2,\ldots\in\{b_1,b_2,\ldots\}$ (otherwise, say $k_i\notin\{b_1,b_2,\ldots\}$, one can delete the $i$th operation without changing the result).

Using the property above, we have the following greedy algorithm.

Let $B[i_1],B[i_2],\ldots$ ($i_1&lt;i_2&lt;\cdots$) be the greatest elements, i.e. $b_1$. The algorithm firstly sets $A[i_1],A[i_2],\ldots$ to $b_1$ using as little operations as possible. More specifically, it checks whether $A[i_1]&gt;b_1$ to see whether an operation is required to set $A[i_1]$ to $b_1$. If so, it then checks whether $A[i_1+1],\ldots,A[i_2-1]\ge b_1$* by range minimum query to see whether this operation can be merged with the operation corresponding to $A[i_2]$. It then goes on with $A[i_2],A[i_3],\ldots$ For example, say

A: 3 3 3 3 2 1 3
B: 2 1 2 1 2 1 2


Now $b_1=2$ and $i_1=0, i_2=2, i_3 = 4, i_4=6$. It requires 2 operations to set $A[i_1],A[i_2],\ldots$ to $b_1$: first setting $A[0], \ldots, A[2]$, then setting $A[6]$.

The algorithm then repeats the above process for $b_2,b_3,\ldots$ 

This algorithm runs in $O(n\log n)$.



*Note, for example, when dealing with $b_2$ instead of $b_1$, no operation can be performed on a range containing $i_j$ for some $j$, otherwise $A[i_j]$ will be less than $B[i_j]$ and cannot be recovered. Therefore we must also check this constraint here. This can be done by maintaining a sorted index array of all elements greater than $b_m$ when dealing with $b_m$.