CF1641B Repetitions Decoding

Olya has an array of integers $ a_1, a_2, \ldots, a_n $ . She wants to split it into tandem repeats. Since it's rarely possible, before that she wants to perform the following operation several (possibly, zero) number of times: insert a pair of equal numbers into an arbitrary position. Help her! More formally: - A tandem repeat is a sequence $ x $ of even length $ 2k $ such that for each $ 1 \le i \le k $ the condition $ x_i = x_{i + k} $ is satisfied. - An array $ a $ could be split into tandem repeats if you can split it into several parts, each being a subsegment of the array, such that each part is a tandem repeat. - In one operation you can choose an arbitrary letter $ c $ and insert $ [c, c] $ to any position in the array (at the beginning, between any two integers, or at the end). - You are to perform several operations and split the array into tandem repeats or determine that it is impossible. Please note that you do not have to minimize the number of operations.

N/A

N/A

In the first test case, you cannot apply operations to the array to make it possible to split it into tandem repeats. In the second test case the array is already a tandem repeat $ [5, 5] = \underbrace{([5] + [5])}_{t_1 = 2} $ , thus we can do no operations at all. In the third test case, initially, we have the following array: $ $$$[1, 3, 1, 2, 2, 3]. $ $ After the first insertion with $ p = 1, c = 3 $ : $ $ [1, \textbf{3, 3}, 3, 1, 2, 2, 3]. $ $ After the second insertion with $ p = 5, c = 3 $ : $ $ [1, 3, 3, 3, 1, \textbf{3, 3}, 2, 2, 3]. $ $ After the third insertion with $ p = 5, c = 3 $ : $ $ [1, 3, 3, 3, 1, \textbf{3, 3}, 3, 3, 2, 2, 3]. $ $ After the fourth insertion with $ p = 10, c = 3 $ : $ $ [1, 3, 3, 3, 1, 3, 3, 3, 3, 2, \textbf{3, 3}, 2, 3]. $ $ The resulting array can be represented as a concatenation of tandem repeats: $ $ \underbrace{([1, 3, 3, 3] + [1, 3, 3, 3])}_{t_1 = 8} + \underbrace{([3, 2, 3] + [3, 2, 3])}_{t_2 = 6}. $ $

In the fourth test case, initially, we have the following array: $ $ [3, 2, 1, 1, 2, 3]. $ $ After the first insertion with $ p = 0, c = 3 $ : $ $ [\textbf{3, 3}, 3, 2, 1, 1, 2, 3]. $ $ After the second insertion with $ p = 8, c = 3 $ : $ $ [3, 3, 3, 2, 1, 1, 2, 3, \textbf{3, 3}]. $ $ After the third insertion with $ p = 5, c = 3 $ $ $ [3, 3, 3, 2, 1, \textbf{3, 3}, 1, 2, 3, 3, 3]. $ $ After the fourth insertion with $ p = 6, c = 2 $ : $ $ [3, 3, 3, 2, 1, 3, \textbf{2, 2}, 3, 1, 2, 3, 3, 3]. $ $ After the fifth insertion with $ p = 7, c = 1 $ : $ $ [3, 3, 3, 2, 1, 3, 2, \textbf{1, 1}, 2, 3, 1, 2, 3, 3, 3]. $ $ The resulting array can be represented as a concatenation of tandem repeats: $ $ \underbrace{([3] + [3])}_{t_1 = 2} + \underbrace{([3, 2, 1] + [3, 2, 1])}_{t_2 = 6} + \underbrace{([1, 2, 3] + [1, 2, 3])}_{t_3 = 6} + \underbrace{([3] + [3])}_{t_4 = 2}. $ $$$