Inaka composes music. Today's arrangement includes a chord of nnn notes that are pairwise distinct, represented by a permutation p1…n of integers from 111 to nnn denoting the notes from the lowest to the highest. Her friend, Miyako, sneaks in and plays a trick by altering the chord with the following two operations: Drop-2: Take out the second highest note and move it to the lowest position, i.e. change the permutation to pn1,p1,p2,…,pn3,pn2,pn. Invert: Take out the lowest note and move it to the highest position, i.e. change the permutation to p2,p3,…,pn1,pn,p1. Any number of consecutive Drop-2 operations is considered a multi-drop. Miyako would like to change the permutation to an ordered permutation, 1,2,…,n, in the fewest number of multi-drops possible. Please help her find the number of multi-drops needed.
Inaka composes music. Today's arrangement includes a chord of nnn notes that are pairwise distinct, represented by a permutation p1…np_{1 dots n}p1…n of integers from 111 to nnn (inclusive) denoting the notes from the lowest to the highest. Her friend, Miyako, sneaks in and plays a trick by altering the chord with the following two operations: Drop-2: Take out the second highest note and move it to the lowest position, i.e. change the permutation to pn−1,p1,p2,…,pn−3,pn−2,pnp_{n-1}, p_1, p_2, dots, p_{n-3}, p_{n-2}, p_npn−1,p1,p2,…,pn−3,pn−2,pn. Invert: Take out the lowest note and move it to the highest position, i.e. change the permutation to p2,p3,…,pn−1,pn,p1p_2, p_3, dots, p_{n-1}, p_n, p_1p2,p3,…,pn−1,pn,p1. Any number of consecutive Drop-2 operations is considered a multi-drop. Miyako would like to change the permutation to an ordered permutation, 1,2,…,n1, 2, dots, n1,2,…,n, in the fewest number of multi-drops possible. Please help her find the number of multi-drops needed.
