CF1558F Strange Sort

You have a permutation: an array $ a = [a_1, a_2, \ldots, a_n] $ of distinct integers from $ 1 $ to $ n $ . The length of the permutation $ n $ is odd. Consider the following algorithm of sorting the permutation in increasing order. A helper procedure of the algorithm, $ f(i) $ , takes a single argument $ i $ ( $ 1 \le i \le n-1 $ ) and does the following. If $ a_i > a_{i+1} $ , the values of $ a_i $ and $ a_{i+1} $ are exchanged. Otherwise, the permutation doesn't change. The algorithm consists of iterations, numbered with consecutive integers starting with $ 1 $ . On the $ i $ -th iteration, the algorithm does the following: - if $ i $ is odd, call $ f(1), f(3), \ldots, f(n - 2) $ ; - if $ i $ is even, call $ f(2), f(4), \ldots, f(n - 1) $ . It can be proven that after a finite number of iterations the permutation will be sorted in increasing order. After how many iterations will this happen for the first time?

N/A

N/A

In the first test case, the permutation will be changing as follows: - after the $ 1 $ -st iteration: $ [2, 3, 1] $ ; - after the $ 2 $ -nd iteration: $ [2, 1, 3] $ ; - after the $ 3 $ -rd iteration: $ [1, 2, 3] $ . In the second test case, the permutation will be changing as follows: - after the $ 1 $ -st iteration: $ [4, 5, 1, 7, 2, 3, 6] $ ; - after the $ 2 $ -nd iteration: $ [4, 1, 5, 2, 7, 3, 6] $ ; - after the $ 3 $ -rd iteration: $ [1, 4, 2, 5, 3, 7, 6] $ ; - after the $ 4 $ -th iteration: $ [1, 2, 4, 3, 5, 6, 7] $ ; - after the $ 5 $ -th iteration: $ [1, 2, 3, 4, 5, 6, 7] $ . In the third test case, the permutation is already sorted and the answer is $ 0 $ .