28659번 - Перестроение лемуров 다국어

Король Джулиан выстроил перед собой $n$ лемуров в шеренгу. Рост каждого лемура это целое число от $1$ до $n$, и любые два лемура имеют разный рост.

Джулиан хочет разделить шеренгу на несколько частей --- непересекающихся подотрезков, которые в объединении дают всю шеренгу. А затем сделать так, чтобы в каждой части лемуры были расположены в порядке возрастания роста слева направо. Если Джулиан решит разбивать шеренгу на $k$ частей, ему нужно будет заплатить лемурам $k \cdot x$ ракушек.

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

Найдите минимальное количество ракушек, которые понадобятся Джулиану, чтобы добиться желаемого.

В первой строке даны два целых числа $n$ и $x$ --- количество лемуров и стоимость одной части ($1 \le n \le 300\,000$, $1 \le x \le 10^9$).

Во второй строке даны $n$ различных чисел от $h_i$ --- высоты лемуров ($1 \le h_i \le n$). Гарантируется, что все $h_i$ различны.

Выведите одно число --- минимальное количество ракушек, которые придется потратить Джулиану, чтобы добиться желаемого.