Перестроение лемуров
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Король Джулиан выстроил перед собой $$$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$$$ различны.

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

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

Примеры

Входные данные
5 1
5 4 3 2 1
Выходные данные
5
Входные данные
1 1
1
Выходные данные
1
Входные данные
10 10
9 10 8 3 7 5 6 2 1 4
Выходные данные
35