На день рождения маленький Ипполит получил долгожданный подарок — набор дощечек с написанными на них буквами латинского алфавита. Теперь-то ему будет чем заняться долгими вечерами, тем более что мама обещала подарить ему в следующем году последовательность целых неотрицательных чисел, если он хорошо освоит этот набор. Ради такого богатства Ипполит готов на многое. Прямо сейчас юный исследователь полностью поглощён изучением хорошести строк. Хорошестью строки называется количество позиций от 1 до L - 1 (где L — длина строки), таких, что следующая буква в строке является следующей по алфавиту. Например, хорошесть строки "" равна 25, а строки "abdc" — только 1.
Ипполит размышляет над решением закономерно возникающей задачи: чему равна максимально возможная хорошесть строки, которую можно собрать, используя дощечки из данного набора? Вы-то и ему с ней справиться.
Формат ввода
Первая строка ввода содержит единственное целое число N — количество различных букв в наборе (1 ≤ N ≤ 26). Обратите внимание: в наборе всегда используются N первых букв латинского алфавита.
Следующие N строк содержат целые положительные числа ci — количество букв соответствующего типа (1 ≤ ci ≤ 109). Таким образом, первое число означает количество букв "a", второе число задаёт количество букв "b" и так далее.
Формат вывода
Выведите единственное целое число — максимально возможную хорошесть строки, которую можно собрать из имеющихся дощечек.
Пример 1
Ввод
3
1
1
1
Вывод
2
Пример 2
Ввод
2
3
4
Вывод
3
Задача заключается в том, чтобы определить максимально возможную хорошесть строки, которую можно собрать из имеющихся дощечек с буквами латинского алфавита. Хорошесть строки - это количество позиций от 1 до L-1, где L - длина строки, таких, что следующая буква в строке является следующей по алфавиту.
Для решения этой задачи, нам необходимо знать количество различных букв в наборе и количество букв каждого типа.
Давайте рассмотрим пример 1 для более ясного понимания.
В примере 1 у нас есть 3 различных буквы в наборе. Количество букв каждого типа равно 1.
Теперь давайте подумаем, какую максимально возможную хорошесть мы можем получить.
Для этого сначала рассмотрим, как хорошо выглядят строки длиной 2. Временно забудем про набор дощечек и рассмотрим все возможные строки длиной 2. Посмотрим, какие из них подходят под определение хорошесть.
Если у нас есть 1 буква каждого типа, то мы можем составить строки "ab", "bc", "cd" и так далее. Всего будет (N-1) таких строк, где N - количество различных букв в наборе. В нашем случае (3-1) = 2. Это значит, что мы можем составить 2 строки длиной 2, которые попадают под определение хорошесть.
Теперь рассмотрим строки длиной 3. Если у нас есть 1 буква каждого типа, то мы можем составить строки "abc", "bcd" и так далее. Всего будет (N-2) таких строк. В нашем случае (3-2) = 1. Это значит, что мы можем составить 1 строку длиной 3, которая попадает под определение хорошесть.
Таким образом, максимально возможная хорошесть для данного набора дощечек будет равна сумме количества строк длиной 2 и длиной 3, то есть (N-1) + (N-2).
Вернемся к примеру 1. У нас N = 3, поэтому максимально возможная хорошесть будет равна (3-1) + (3-2) = 2 + 1 = 3.
Ответ: 3.
Теперь попробуйте решить пример 2 самостоятельно, следуя аналогичному подходу.
Если у вас возникнут еще вопросы, пожалуйста, не стесняйтесь задавать их. Я всегда готов помочь!