Кеша участвует в соревнованиях по программированию. По правилам соревнований участники упорядочиваются по количеству решённых задач, а при равенстве — по количеству штрафных баллов.
Один штрафной балл начисляется за одну неудачную попытку по задаче, которая в итоге была решена участником. Например, если участник сделал три неудачных попытки решить задачу, а в четвёртый раз решил задачу правильно, за эту задачу будет начислено три штрафных балла.
Если участник не смог решить задачу, штрафные баллы за неё не начисляются.
Кеша мог делать попытки решения задач в любом порядке. Он мог сделать неудачную попытку по некоторой задаче, затем сделать попытки по другим задачам (возможно, успешные) и вновь вернуться к той, которую не решил.
К моменту окончания соревнования Кеша решил $$$k$$$ задач. Известно, что:
Вам дан список номеров задач в той последовательности, в которой Кеша делал попытки их решить.
Ваша задача — посчитать количество штрафных баллов, которые будут начислены Кеше.
В первой строке содержится целое число $$$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)$$$, номера задач в той последовательности, в которой Кеша делал по ним попытки.
Выведите единственное целое число — количество штрафных баллов, которые будут начислены Кеше.
В первой, второй и третьей подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.
Для решения второй подзадачи требуется, чтобы программа верно решала первую позадачу.
В четвёртой подзадаче баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.
Также для четвёртой подзадачи требуется, чтобы программа верно решала предшествующие подзадачи.
Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 2 (до 10) | $$$m, \, p \le 10$$$ | нет | полная |
| 2 | 2 (до 30) | $$$m, \, p \le 1000$$$ | 1 | полная |
| 3 | 2 (до 10) | $$$k = 1$$$ | нет | полная |
| 4 | 0 (50) | любые допустимые значения | 1, 2, 3 | первая ошибка |
3105228527582
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$$$ штрафных баллов.