Перестроение лемуров
Перестроение лемуров
Король Джулиан выстроил перед собой n лемуров в шеренгу. Рост каждого лемура это целое число от 1 до n, и любые два лемура имеют разный рост.
Джулиан хочет разделить шеренгу на несколько частей непересекающихся подотрезков, которые в объединении дают всю шеренгу. А затем сделать так, чтобы в каждой части лемуры были расположены в порядке возрастания роста слева направо. Если Джулиан решит разбивать шеренгу на k частей, ему нужно будет заплатить лемурам k * x ракушек.
После того, как Джулиан разобьет шеренгу на части, он может произвольное количество раз за одну ракушку поменять местами двух лемуров, стоящих рядом в одной части.
Найдите минимальное количество ракушек, которые понадобятся Джулиану, чтобы добиться желаемого.
Входные данные
В первой строке даны два целых числа n и x (1 ≤ n ≤ 300 000, 1 ≤ x ≤ 109
) - количество лемуров и стоимость одной части.
Во второй строке даны n различных чисел hi
(1 ≤ hi
≤ n) - высоты лемуров. Гарантируется, что все hi
различны.
Выходные данные
Выведите одно число - минимальное количество ракушек, которые придется потратить Джулиану, чтобы добиться желаемого.
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