If \(A\) and \(B\) do not coincide as multisets, the objective is obviously unachievable. Below, we assume these multisets are the same.

First, let us solve the case in which the values of \(A\) are distinct. Consider the parity of the inversion number of the sequence \(A\). This is unaffected by the operation. On the other hand, if the parity of the inversion number of \(A\) and that of \(B\) are the same, it turns out that \(A\) can be changed to \(B\).

We can show this as follows. First, if \(N \geq 3\), we can bring any value to the front by some sequence of operations. By repeating this for the \(1\)-st, \(2\)-nd, \(\cdots\), \((N-2)\)-th terms from the left in \(B\), we can match the first \(N-2\) terms of \(A\) and \(B\). What remains is the order of the remaining \(2\) terms, but this is determined by the parity of the inversion number, so \(A\) and \(B\) are guaranteed to coinside.

Finally, let us consider the case in which there are duplicates among the values of \(A\). In this case, it turns out that \(A\) can always be changed to \(B\). Specifically, we first make all values distinct by labeling duplicated values (for example, label the occurrences of \(v\) as \(v_1,v_2,\cdots\)). If \(A\) and \(B\) now have the same parity of the inversion number, we are done. If they do not, we swap the labels of \(v_1\) and \(v_2\) in \(A\). This changes the parity of the inversion number, allowing us to apply the procedure in the “distinct” case.

We can now solve the problem by directly implementing this criterion. It can be solved in \(O(N\log N)\) time, but the constraints allow \(O(N^2)\) solutions.

Sample submission (c++)