P5868 [SEERC 2018] Min Max Convert

$A$ is an array with $N$ elements. You can perform the following two operations on this array: 1. Choose an index interval $[a, b] \ (1 \leq a \leq b \leq N)$. Let the maximum value among the elements in this interval be $x$, and replace all elements in this interval with $x$. 2. Choose an index interval $[a, b] \ (1 \leq a \leq b \leq N)$. Let the minimum value among the elements in this interval be $x$, and replace all elements in this interval with $x$. Compute a sequence of operations that transforms array $A$ into another given array $B$ (also with $N$ elements). The number of operations in the sequence must be less than or equal to $2N$.

The first line contains an integer $N$. The second line contains an array $A$ with $N$ elements. The third line contains another array $B$ with $N$ elements.

If there is no solution, output $-1$. Otherwise, output an integer $x$ in the first line, representing the minimum number of operations needed to transform array $A$ into $B$. In the next $x$ lines, each line contains one character (representing the type of operation, `m ` means the minimum-value operation is used, and `M` means the maximum-value operation is used) and an interval $(a,b)$, describing each operation. If there are multiple solutions, output any one of them.

- $1 \leq N \leq 100, 000$. - All elements in arrays $A$ and $B$ are integers in the interval $[1, N]$. Translated by ChatGPT 5