Легендарные Четыре Всадника готовят для своего выступления трюк под названием <<Вечный двигатель>>. Для его реализации они создали механизм, представляющий собой выстроенные в ряд $n$ шестерёнок с различным количеством зубьев $a_1, a_2, ..., a_n$.

К сожалению, оказалось, что механизм не работает так, как нужно, поэтому Всадники принялись искать проблему. В результате нескольких бессонных ночей и долгих сложнейших расчётов они выяснили, что шестерёнки расставлены в неверном порядке~--- в верном механизме шестерёнки должны быть расположены так, что последняя, самая правая, шестерня вращается максимально быстро при вращении первой, самой левой, с определённой постоянной скоростью.

До выступления осталось совсем немного, а разбирать и собирать механизм заново~--- дело небыстрое. К счастью, механизм починить всё же можно, ведь ловкие руки иллюзиониста могут довольно быстро менять местами две соседние шестерёнки. После долгих поисков ошибки Всадники очень устали и хотят скорее отправиться отдыхать перед выступлением, поэтому им нужно узнать, какое минимальное количество обменов необходимо для починки механизма.