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

Кеша участвует в соревнованиях по программированию. По правилам соревнований участники упорядочиваются по количеству решённых задач, а при равенстве — по количеству штрафных баллов.

Один штрафной балл начисляется за одну неудачную попытку по задаче, которая в итоге была решена участником. Например, если участник сделал три неудачных попытки решить задачу, а в четвёртый раз решил задачу правильно, за эту задачу будет начислено три штрафных балла.

Если участник не смог решить задачу, штрафные баллы за неё не начисляются.

Кеша мог делать попытки решения задач в любом порядке. Он мог сделать неудачную попытку по некоторой задаче, затем сделать попытки по другим задачам (возможно, успешные) и вновь вернуться к той, которую не решил.

К моменту окончания соревнования Кеша решил $$$k$$$ задач. Известно, что:

  • если Кеша решил некоторую задачу, он больше не делал по ней ни одной попытки;
  • если Кеша решил задачу с номером $$$X$$$, то он решил все задачи с номерами, меньшими $$$X$$$, по которым он сделал хотя бы одну попытку.

Вам дан список номеров задач в той последовательности, в которой Кеша делал попытки их решить.

Ваша задача — посчитать количество штрафных баллов, которые будут начислены Кеше.

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

В первой строке содержится целое число $$$k$$$ $$$(1 \le k \le 10^5)$$$ — количество задач, решённых Кешей.

Во второй строке содержится целое число $$$m$$$ $$$(k \le m \le 3 \cdot 10^5)$$$ — количество попыток, сделанных Кешей.

В каждой из следующих $$$m$$$ строк содержится по одному целому числу $$$p_i$$$ $$$(1 \le p_i \le 10^6, \, i = 1, 2, \ldots, m)$$$, номера задач в той последовательности, в которой Кеша делал по ним попытки.

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

Выведите единственное целое число — количество штрафных баллов, которые будут начислены Кеше.

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

В первой, второй и третьей подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

Для решения второй подзадачи требуется, чтобы программа верно решала первую позадачу.

В четвёртой подзадаче баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.

Также для четвёртой подзадачи требуется, чтобы программа верно решала предшествующие подзадачи.

Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
12 (до 10)$$$m, \, p \le 10$$$нетполная
22 (до 30)$$$m, \, p \le 1000$$$1полная
32 (до 10)$$$k = 1$$$нетполная
40 (50)любые допустимые значения1, 2, 3первая ошибка

Пример
Входные данные
3
10
5
2
2
8
5
2
7
5
8
2
Выходные данные
5
Примечание

В приведенном примере Кеша сделал $$$10$$$ попыток и решил $$$3$$$ задачи.

Он пытался решать задачи с номерами $$$5$$$, $$$2$$$, $$$8$$$ и $$$7$$$ и справился со всеми, кроме задачи $$$8$$$.

Если предположить, что Кеша решил задачу $$$8$$$, то он должен был решить и задачу $$$5$$$, и задачу $$$2$$$, и задачу $$$7$$$, поскольку они имеют меньшие номера. Но в этом случае он решил бы $$$4$$$ задачи, что неверно.

Посчитаем штрафные баллы. Изначально их у Кеши $$$s = 0$$$.

Первая попытка по задаче $$$5$$$ была неудачной. Однако эту задачу Кеша в итоге решил, поэтому за нее начисляется штрафной балл, $$$s = 1$$$.

Первая попытка по задаче $$$2$$$ также была неудачной, но и эту задачу Кеша решил, поэтому за нее также будет начислен штрафной балл, $$$s = 2$$$.

Вторая попытка по задаче $$$2$$$ не привела к успеху, $$$s = 3$$$.

Первая попытка по задаче $$$8$$$ была неудачной, но, поскольку Кеша так и не решил эту задачу, количество штрафных баллов останется без изменений: $$$s = 3$$$.

Далее следует вторая неудачная попытка по задаче $$$5$$$, и $$$s = 4$$$.

Ещё одна (третья) неудачная попытка по задаче $$$2$$$ приведёт к начислению ещё одного штрафного балла, $$$s = 5$$$.

Затем Кеша с первой попытки решает задачу $$$7$$$, штрафные баллы за неё не начисляются.

После этого Кеша, наконец, справляется с задачей $$$5$$$ — и за удачную попытку штрафные баллы не начисляются.

Вторая попытка по задаче $$$8$$$ не приводит к успеху, однако и не увеличивает количество штрафных баллов.

Наконец, Кеша предпринимает четвёртую попытку сдать задачу $$$2$$$, и ему сопутствует успех. Количество штрафных баллов остается прежним.

Таким образом, Кеше будет начислено $$$5$$$ штрафных баллов.