| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 8 | 6 | 5 | 71.429% |
Король Джулиан выстроил перед собой $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