Оптимальное перестроение

Сегодня Аквамен решил навести порядок в своем огромном отряде из рыб. Для этого он выстроил их перед собой и стал внимательно изучать.

Всего у Аквамена есть $n$ рыб, стоящих в ряд. Самой главной характеристикой рыбы является ее сила. Сила $i$-й рыбы от начала ряда равна $a\_i$. Отряд рыб подобран идеально: сила каждой рыбы является целым числом от $1$ до $n$, а также ни у каких двух рыб силы не совпадают. Иными словами, силы рыб образуют перестановку.

Назовем беспорядочностью ряда из рыб количество пар рыб, в которых более сильная рыба стоит в ряду раньше, чем менее сильная. Иными словами, беспорядочность ряда --- это количество пар номеров рыб $i$ и $j$, для которых $i < j$ и $a\_i > a\_j$.

Аквамен может отдать одну команду перестроения отряду. Для этого он должен назвать целое число $x$ от $1$ до $n$. После этого рыбы образуют новый ряд, в котором сначала стоят рыбы с силой, меньшей $x$, потом стоит рыба с силой ровно $x$, а потом стоят рыбы с силой, большей $x$. При этом рыбы, сила которых меньше или больше, чем $x$, не меняют своего относительного порядка при перестроении. Например, если рыбы стояли в порядке $\\{3, 6, 1, 4, 2, 5\\}$, и Аквамен выбрал значение $x = 4$, то после перестроения рыбы будут стоять в порядке $\\{3, 1, 2, 4, 6, 5\\}$.

Аквамен хочет отдать одну команду перестроения, чтобы после выполнения этой команды беспорядочность ряда рыб была как можно меньше. Помогите ему определить, какое минимальное значение беспорядочности он может получить.

Первая строка входных данных содержит единственное целое число $n$ --- количество рыб в ряду ($1 \le n \le 3\\,000\\,000$).

Вторая строка содержит $n$ различных целых чисел $a\_1, a\_2, \ldots, a\_n$ --- значения сил рыб в ряду ($1 \le a\_i \le n$, $a\_i \neq a\_j$ для всех $i \neq j$).

Выведите единственное целое число --- минимальную беспорядочность, которую может иметь ряд из рыб после одной команды перестроения.