Юный программист Кеша сегодня участвует в соревнованиях по программированию. До места соревнований он добирается на трамвае, и ехать ему предстоит достаточно долго. В дороге Кеша обычно читает разные интересные статьи.
У Кеши на смартфоне открыты $$$n$$$ статей, которые он хотел бы прочитать. Будем считать их занумерованными от $$$1$$$ до $$$n$$$. Для чтения Кеша всегда выбирает самую короткую статью из ещё не прочитанных. Если есть несколько статей, требующих одинакового времени на чтение, Кеша всегда выбирает статью с меньшим номером.
По дороге Кеша прочитал все $$$n$$$ статей. Известен порядок номеров статей $$$a_1, a_2, \ldots, a_n$$$, в котором Кеша их читал.
Кеша обратил внимание, что на чтение статьи с номером $$$a_1$$$ он потратил время $$$t_{a_1} = 1$$$. Кроме того, он заметил, что для каждой пары статей с номерами $$$a_j$$$ и $$$a_{j+1}$$$ верно одно из двух: либо $$$t_{a_{j+1}} = t_{a_j}$$$, либо $$$t_{a_{j+1}} = t_{a_j} + 1$$$.
Ваша задача — определить минимально возможное и максимально возможное время, которое Кеша мог потратить на чтение всех статей.
В первой строке содержится целое число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество статей, прочитанных Кешей.
В каждой из следующих $$$n$$$ строк содержится по одному целому числу $$$a_j$$$ $$$(1 \le a_j \le n, j = 1, 2, \ldots, n)$$$ — номеру очередной статьи, которую читал Кеша.
Гарантируется, что для любых $$$i$$$ и $$$j$$$ верно, что если $$$i \not= j$$$, то и $$$a_i \not= a_j$$$.
Выведите два целых числа —минимально возможное время, которое Кеша мог потратить на чтение всех статей, и максимально возможное время, которое Кеша мог потратить на чтение всех статей. Разделяйте числа пробелом или переводом строки.
Обратите внимание, что ответ может превышать возможное значение $$$32$$$-битной целочисленной переменной, поэтому необходимо использовать $$$64$$$-битные целочисленные типы данных (тип $$$int64$$$ в языке $$$Pascal$$$, тип $$$long \, long$$$ в $$$C++$$$, тип $$$long$$$ в $$$Java$$$ и $$$C\#$$$).
В во всех трех подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.
Для второй подзадачи требуется, чтобы программа верно решала первую подзадачу, для третьей подзадачи требуется, чтобы программа верно решала первую и вторую подзадачи. Более подробно разбиение на подзадачи показано в таблице ниже.
Тесты из условия не оцениваются.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 1 (до 10) | $$$n \le 10$$$ | нет | полная |
| 2 | 5 (до 50) | $$$n \le 1000$$$ | 1 | полная |
| 3 | 5 (до 40) | $$$n \le 10^5$$$ | 1, 2 | полная |
42314
6 10
Поясним приведённый пример.
Минимальное время прочтения всех статей достигается при $$$t_2 = t_3 = 1$$$ и $$$t_1 = t_4 = 2$$$ — суммарно $$$2 + 1 + 1 + 2 = 6$$$.
Максимальное время прочтения всех статей достигается при $$$t_2 = 1$$$, $$$t_3 = 2$$$, $$$t_1 = 3$$$ и $$$t_4 = 4$$$— суммарно $$$3 + 1 + 2 + 4 = 10$$$.
Кеша участвует в соревнованиях по программированию. По правилам соревнований участники упорядочиваются по количеству решённых задач, а при равенстве — по количеству штрафных баллов.
Один штрафной балл начисляется за одну неудачную попытку по задаче, которая в итоге была решена участником. Например, если участник сделал три неудачных попытки решить задачу, а в четвёртый раз решил задачу правильно, за эту задачу будет начислено три штрафных балла.
Если участник не смог решить задачу, штрафные баллы за неё не начисляются.
Кеша мог делать попытки решения задач в любом порядке. Он мог сделать неудачную попытку по некоторой задаче, затем сделать попытки по другим задачам (возможно, успешные) и вновь вернуться к той, которую не решил.
К моменту окончания соревнования Кеша решил $$$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$$$ штрафных баллов.
Юный программист Кеша принял участие в соревнованиях по программированию и вместе со своими друзьями — Лизой, Мишей и Настей — ожидает объявления итогов.
Организаторы приготовили разные шуточные призы для лучших участников и решили выложить их на столе и позволить каждому из участников выбрать приз самостоятельно. Первым будет выбирать приз тот, кто занял первое место, вторым — тот, кто занял второе место и так далее.
Кеша и его друзья увидели среди призов четыре музыкальных инструмента: барабан, бубен, вувузелу и губную гармошку. Оказалось, что у каждого из ребят есть предпочитаемый музыкальный инструмент, который они хотели бы получить в качестве приза. Впрочем, если к моменту, когда подойдет их очередь выбирать приз, именно этого инструмента уже не будет, у каждого из них есть второй предпочитаемый музыкальный инструмент. Если же и второй предпочитаемый инструмент будет отсутствовать, они выберут какой-то другой приз.
Вам известны первый и второй предпочитаемые инструменты для каждого из ребят. Ваша задача — определить, в какой последовательности они должны занять места, чтобы каждый смог взять себе какой-либо из желаемых музыкальных инструментов. Можете считать, что все остальные участники не выберут себе в качестве приза музыкальные инструменты.
Ради упрощения обозначим музыкальные инструменты заглавными латинскими буквами:
В первой строке содержится целое число $$$t$$$ $$$(1 \le t \le 5000)$$$ — количество тестов.
Далее следует $$$t$$$ групп по 4 строки.
В первой строке группы содержатся два символа без пробела, обозначающие первый и второй предпочитаемые инструменты Кеши.
Во второй строке группы содержатся два символа без пробела, обозначающие первый и второй предпочитаемые инструменты Лизы.
В третьей строке группы содержатся два символа без пробела, обозначающие первый и второй предпочитаемые инструменты Миши.
В четвертой строке группы содержатся два символа без пробела, обозначающие первый и второй предпочитаемые инструменты Насти.
Гарантируется, что для каждого из ребят первый и второй предпочитаемые инструменты не совпадают.
Выведите $$$t$$$ строк из четырех символов $$$K$$$ (Кеша), $$$L$$$ (Лиза), $$$M$$$ (Миша), $$$N$$$ (Настя) без пробелов, показывающую последовательность, в которой ребята должны занять места, чтобы каждый имел возможность выбрать один из предпочитаемых музыкальных инструментов.
Если такой последовательности не существует, выведите строку $$$UUUU$$$.
Если для какого-либо теста существует более одного правильного ответа, выводите любой из них.
В первой и второй подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.
В третьей подзадаче баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.
Для второй и третьей подзадач требуется, чтобы программа верно решала предшествующие подзадачи. Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 2 (до 10) | $$$t = 1$$$ | нет | полная |
| 2 | 3 (до 30) | $$$2 \le t \le 10$$$ | 1 | полная |
| 3 | 0 (60) | любые допустимые значения t | 1,2 | первая ошибка |
4BCBACDABABBAABCDABBAADADCDACBAAB
NLKM UUUU UUUU NMLK
Поясним приведённый пример.
В нём содержится $$$4$$$ теста.
Первый тест
Ребята хотят получить следующие инструменты:
Если ребята займут места в порядке NLKM, то
Обратите внимание, что ответы LNKM, LKNM и LKMN также являются корректными.
Второй тест
Ребята хотят получить следующие инструменты:
Как можно видеть, Кеша, Лиза и Миша хотят получить только инструменты $$$A$$$ или $$$B$$$. Очевидно, что при любом раскладе один из них не получит желаемый инструмент.
Третий тест
Ребята хотят получить следующие инструменты:
Как можно видеть, на четверых участников приходится $$$3$$$ желаемых инструмента (никто не хочет $$$C$$$). Очевидно, что при любом раскладе один из них не получит желаемый инструмент.
Четвёртый тест
Ребята хотят получить следующие инструменты:
Если ребята займут места в порядке NMLK, то
Обратите внимание, что ответы MNLK, NLMK и NLKM также являются корректными.
Кеша участвует в соревнованиях по программированию. Его друг Прохор не особенно интересуется алгоритмическим программированием, поэтому просто наблюдает за соревнованиями со стороны: просматривает приходящие уведомления и таблицу результатов.
По правилам соревнований участники упорядочиваются по количеству решенных задач; участник, решивший наибольшее количество задач, занимает первое место и т.д. При равном количестве решенных задач используются дополнительные критерии, но Прохор не хочет в них разбираться. Ему достаточно знать диапазон мест, занятых участниками с таким же количеством задач, которое в данный момент решил Кеша.
Каждый раз, когда какой-либо участник решает какую-либо задачу, приходит уведомление об этом. Для упрощения будем считать, что уведомление содержит только номер участника. Кеша получил номер участника $$$1$$$.
В некоторые моменты Прохор интересуется, в каком диапазоне мест находится сейчас Кеша. Это значит, что он хочет узнать два числа:
Ваша задача — получить ответы на вопросы Прохора.
В первой строке содержится целое число $$$n$$$ $$$(2 \le n \le 3 \cdot 10^5)$$$ — суммарное количество уведомлений и запросов Прохора.
Во второй строке содержится $$$n$$$ целых чисел $$$q_j$$$ $$$(0 \le q_j \le 10^6, \, j = 1, 2, \ldots, n)$$$ через пробел:
Гарантируется, что:
Для каждого $$$q_j = 0$$$ выведите два целых числа — наиболее высокое и наименее высокое места участников, решивших в этот момент столько же задач, сколько и Кеша.
Разделяйте числа пробелом или переводом строки.
В первой и второй подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.
Для решения второй подзадачи требуется, чтобы программа верно решала первую подзадачу.
В третьей подзадаче баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.
Также для третьей подзадачи требуется, чтобы программа верно решала предшествующие подзадачи.
Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 2 (до 10) | $$$\max\limits_{j=1}^{n}{q_j} \le 10, \, n \le 100$$$ | нет | полная |
| 2 | 2 (до 30) | $$$\max\limits_{j=1}^{n}{q_j}, \, n \le 1000$$$ | 1 | полная |
| 3 | 0 (60) | любые допустимые значения | 1, 2 | первая ошибка |
25 2 7 1 2 0 3 7 1 0 2 2 0 5 7 0 5 0 3 1 0 1 0 2 7 0
2 3 1 3 2 3 3 3 3 4 2 3 1 2 2 3
Поясним приведённый пример.
Очень часто на пробном туре соревнований участникам предлагается задача $$$A + B$$$. Организаторы соревнований, в которых участвует Кеша, так и поступили. А на основном туре предложили другую задачу, $$$B + C$$$.
Кеше нравятся короткие условия, поэтому он сразу же взялся решать эту задачу.
На доске записали равенство $$$A = B + C$$$, где $$$A$$$, $$$B$$$ и $$$C$$$ — целые положительные числа без ведущих нулей.
Затем некоторые цифры в равенстве стёрли.
Ваша задача (и Кеши, конечно, тоже) — определить, сколькими способами можно восстановить стёртые цифры, чтобы равенство осталось верным.
В первой строке записано число $$$A$$$ $$$(1 \le |A| \le 100)$$$ — последовательность десятичных цифр и символов # без пробелов.
Во второй строке записано число $$$B$$$ $$$(1 \le |B| \le 100)$$$ — последовательность десятичных цифр и символов # без пробелов.
В третьей строке записано число $$$C$$$ $$$(1 \le |C| \le 100)$$$ — последовательность десятичных цифр и символов # без пробелов.
Символы # заменяют стёртые цифры.
Гарантируется, что $$$A$$$, $$$B$$$, $$$C$$$:
Обозначим через $$$m$$$ количество способов заменить знаки # на десятичные цифры 0-9 согласно условию задачи. Поскольку число $$$m$$$ может быть очень большим, выведите остаток от деления $$$m$$$ на $$$10^9 + 7$$$.
Способ считается верным, если при замене цифр:
Во всех подзадачах баллы начисляются только в случае прохождения всех тестов этой подзадачи и необходимых подзадач.
Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 0 (10) | $$$|A|, |B|, |C| \le 3$$$ | нет | первая ошибка |
| 2 | 0 (10) | $$$|A|, |B|, |C| \le 5$$$, $$$A$$$ не содержит # | нет | первая ошибка |
| 3 | 0 (10) | $$$|A|, |B| \le 5$$$, $$$|C| \le 2$$$ | нет | первая ошибка |
| 4 | 0 (10) | $$$|A|, |B|, |C| \le 5$$$ | 1, 2, 3 | первая ошибка |
| 5 | 0 (15) | $$$A$$$ не содержит #, $$$|C| \le 2$$$ | нет | первая ошибка |
| 6 | 0 (15) | $$$A$$$ не содержит # | 2, 5 | первая ошибка |
| 7 | 0 (15) | $$$|C| \le 2$$$ | 3, 5 | первая ошибка |
| 8 | 0 (15) | любые допустимые значения | 4, 6, 7 | первая ошибка |
12##457
1
968#0#8#
0
9##
8
Поясним приведённые примеры.
Первый пример Единственный возможный способ восстановить значения:
Второй пример
Невозможно восстановить ни одним способом.
Как легко заметить, в числе $$$B$$$ десятков $$$0$$$, в $$$C$$$ десятков $$$8$$$, а в числе $$$A$$$ десятков $$$6$$$.
Третий пример
Подойдут следующие способы: