Из-за нехватки преподавателей в самой высокой параллели «Т-поколения» было принято решение поставить огромного самца гориллы принимать зачет у школьников. Но не все так просто, для того чтобы доказать свою компетентность, ему нужно решить следующую задачу.
Для массива \(b\) определим функцию \(f(b)\) как минимальное количество следующих операций, чтобы сделать массив \(b\) пустым:
- взять два целых числа \(l\) и \(r\), такие что \(l \le r\), пусть \(\min(b_l, b_{l+1}, \ldots, b_r)\) равен \(x\), затем
- удалить из массива все такие \(b_i\), что \(l \le i \le r\) и \(b_i = x\), удаленные элементы удаляются, индексы перенумеруются
Дан массив \(a\) длины \(n\) и целое число \(k\). Вы можете не более \(k\) раз выбрать любой индекс \(i\) (\(1 \le i \le n\)) и произвольное число \(p\), и заменить \(a_i\) на \(p\).
Помогите горилле и определите, какое минимальное значение \(f(a)\) можно получить после таких замен.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите одно целое число — минимальное значение \(f(a)\).
Примечание
В первом наборе входных данных \(f([48\,843]) = 1\), так как массив состоит из одного числа, а значит, можно его удалить за одну операцию.
Во втором наборе входных данных можно изменить второе число на \(2\), получив массив \([2, 2, 2]\), \(f([2, 2, 2]) = 1\), так как можно взять в качестве подотрезка весь массив, минимум на нем равен \(2\), поэтому мы удалим все числа \(2\) из массива, и массив станет пустым.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 0
48843
3 1
2 3 2
5 3
1 2 3 4 5
7 0
4 7 1 3 2 4 1
11 4
3 2 1 4 4 3 4 2 1 3 3
5 5
1 2 3 4 5
|
1
1
2
5
2
1
|