После четвёртого сезона Шерлок и Мориарти осознали бессмысленность баталии, развернувшейся между ними, и решили дальше соревноваться в мирную игру «Банковские карты».
Правила у этой игры предельно просты: каждый игрок приносит свою любимую банковскую карту с n-значным номером. Далее оба игрока по очереди называют последовательные цифры из банковской карты. Если цифры не совпадают, то участник, цифра которого оказывается меньше, получает щелбан от другого игрока. Например, если n = 3 и у Шерлока номер карты 123, а у Мориарти 321, то сначала Шерлок называет число 1, а Мориарти называет число 3 и Шерлок получает щелбан. Затем и Шерлок и Мориарти называют число 2, и щелбан не получает никто. Наконец на третьем шаге, Шерлок называет 3, а Мориарти называет 1 и получает щелбан.
Шерлок, конечно, будет играть честно, но Мориарти, как настоящий злодей, подсмотрел номер карты Шерлока и теперь хочет называть цифры своей банковской карты не последовательно, а в некотором другом порядке (однако количество каждой из цифр он не изменяет). Например в случае выше, Мориарти мог бы назвать цифры в последовательности 1, 2, 3 и не получил бы щелбанов вообще, а мог назвать 2, 3 и 1 и выдать Шерлоку целых два щелбана.
Вам поручено вычислить, какое минимальное количество щелбанов Мориарти точно получит и какое максимальное число Мориарти может дать Шерлоку. Обратите внимание, что это две разные цели, и они могут достигаться при использовании разных порядков.
Выходные данные
Сначала выведите минимальное число щелбанов, которое обязательно получит Мориарти. Затем выведите максимальное число щелбанов, которое Мориарти может дать Шерлоку.