Вечный двигатель
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

Входные данные

Первая строка содержит целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество шестерёнок.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_i$$$, где $$$i$$$-е число описывает количество зубчиков у $$$i$$$-й шестерёнки ($$$2 \le a_i \le 10^{18}$$$).

Выходные данные

Выведите одно число — минимальное количество обменов, необходимое для починки механизма.

Примеры

Входные данные

    53 7 2 2 4

Выходные данные

    2

Входные данные

    72 8 2 2 8 3 4

Выходные данные

    4

Входные данные

    89 10 5 4 5 7 7 2

Выходные данные

    1