CF1698F Equal Reversal

There is an array $ a $ of length $ n $ . You may perform the following operation on it: - Choose two indices $ l $ and $ r $ where $ 1 \le l \le r \le n $ and $ a_l = a_r $ . Then, reverse the subsegment from the $ l $ -th to the $ r $ -th element, i. e. set $ [a_l, a_{l + 1}, \ldots, a_{r - 1}, a_r] $ to $ [a_r, a_{r-1}, \ldots, a_{l+1}, a_l] $ . You are also given another array $ b $ of length $ n $ which is a permutation of $ a $ . Find a sequence of at most $ n^2 $ operations that transforms array $ a $ into $ b $ , or report that no such sequence exists.

N/A

N/A

In the first test case, we can perform the following operations: $ $$$[1,2,4,3,1,2,1,1] \xrightarrow[l=5,\,r=8]{} [1,2,4,3,1,1,2,1] \xrightarrow[l=1,\,r=6]{} [1,1,3,4,2,1,2,1]. $ $

In the second test case, we can perform the following operations: $ $ [1,2,3,1,3,2,3] \xrightarrow[l=1,\,r=4]{} [1,3,2,1,3,2,3] \xrightarrow[l=3,\,r=6]{} [1,3,2,3,1,2,3]. $ $

It can be proven that it is impossible to turn $ a $ into $ b$$$ in the third and fourth test cases.