Statement is not available in English language
2. Задача B. Казино
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Второй тур кончился, чему очень рад Егор, ведь он не ставил фьючерсы уже целых $$$5$$$ часов.

Монеты, на которые Егор может поставить фьюч, можно представить в виде множества $$$S$$$ всех целых чисел от $$$1$$$ до $$$m$$$, то есть $$$ \{\, x \in S \mid 1 \leq x \leq m \, \} $$$. Но поскольку не на все монеты выгодно ставить деньги, у него есть специальное подмножество самых прибыльных монет $$$P$$$ размером $$$n$$$.

Но зайдя в бинанс Егор ужаснулся — какой-то гад поставил фьючи на все монеты сразу. Ему надо срочно все исправить, то есть сделать из множества $$$S$$$ множество $$$P$$$. Сделать это он может с помощью двух операций:

  • Удалить любой элемент из множества $$$S$$$. Из-за комиссии стоимость данной операции $$$1$$$ near.
  • Удалить элемент из множества $$$S$$$ равный $$$MEX-i$$$, где $$$MEX$$$ — это минимальное натуральное число, которое не встречается в множестве $$$S$$$, $$$i$$$ — это номер текущий операции в единичной индексации. Стоимость данной операции $$$0$$$ near.

Помогите Егору получить множество $$$P$$$ из $$$S$$$ за минимальное количество near.

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

В первой строке заданы два целых положительных числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq m \leq 10^4$$$).

Следующая строка содержит $$$n$$$ целых различных чисел $$$p_1,p_2,\dots,p_n$$$ ($$$1 \leq p_i \leq m$$$), разделенных пробелами — описание множества $$$P$$$. Гарантируется, что $$$p_i \leq p_{i+1}$$$.

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

Выведите минимальное количество near.

Система оценки

Определим $$$ A = S \setminus P $$$. То есть $$$ A $$$  — множество элементов, которые необходимо удалить.

№Дополнительные ограниченияБаллы за подзадачуНеобходимые подзадачи
$$$1$$$$$$m \leq 11$$$$$$7$$$
$$$2$$$$$$m \leq 22$$$$$$12$$$$$$1$$$
$$$3$$$$$$m \leq 500$$$$$$16$$$$$$1, 2$$$
$$$4$$$$$$A_{m - n} = m - 1; A_i = A_{i + 1} - (m - n - i + 1) $$$$$$6$$$
$$$5$$$$$$ A_i - A_{i - 1} = A_{i + 1} - A_i $$$$$$14$$$
$$$6$$$Нет дополнительных ограничений$$$45$$$$$$1$$$ — $$$5$$$
Примеры
Входные данные
2 4
2 4
Выходные данные
1
Входные данные
3 3
1 2 3
Выходные данные
0
Примечание

Рассмотрим первый пример из условия. Изначально $$$MEX$$$ множества равен $$$m + 1 = 5$$$. Первой операцией мы не можем удалить элемент $$$MEX - 1 = 4$$$, так как он должен остаться. Поэтому удалим элемент 3 за $$$1$$$ near. После чего второй операцией мы можем удалить элемент $$$MEX - 2 = 3 - 2 = 1$$$ за $$$0$$$ near.