Решение задач Yandex Cup 2023 на Java
Аркадий — главный редактор журнала по арт-критике. По долгу службы Аркадий постоянно сталкивается с фундаментальными вопросами «Что есть красота?», «Как понять что красиво, а что нет?».
Главред понимает, что искусство можно оценивать по-разному и к разным арт-объектам можно применять разные метрики. За годы работы в арт-индустрии Аркадий выработал собственный принцип оценки красоты любого произведения искусства. Он может сказать, красив арт-объект или нет, вне зависимости от количества критериев оценки «красивости».
Принцип Аркадия состоит в следующем. Для произвольного объекта искусства определяется некоторое количество критериев в определенном порядке для оценки «красивости». По каждому критерию можно набрать максимум n первичных баллов. Вторичные баллы за условный критерий i определяются следующим образом:
Если при оценке критерия набирается ai первичных баллов, то Аркадий начисляет критерию a2iвторичных баллов.
Кроме того, Аркадий прибавляет бонусные баллы за ai следующих ненулевых оценок по другим критериям (прибавляются первичные баллы).
Для последнего критерия дополнительные баллы не начисляются.
Например, если n = 10, Аркадий оценивал картину по пяти критериям, и арт-объект набрал [10, 0, 1, 0, 3] первичных баллов, соответственно, то его итоговый результат будет равен 117 вторичных баллов, так как за первый критерий он получил 102 + 1 + 3 балла, за второе и четвертое — по 0, за третье — 12 + 3, за пятое — 32.
Аркадий дал последовательность результатов m оценок критериев произведения искусства. Определите общую сумму вторичных баллов.
Формат ввода:
В первой строке даны два целых числа n и m (1 ≤ n, m ≤ 200 000).
Во второй строке заданы m целых чисел ai (0 ≤ ai ≤ n).
Формат вывода:
Выведите сумму набранных баллов.
Пример 1:
Ввод:
10 5
10 0 1 0 3
Вывод:
117
Пример 2:
Ввод:
5 5
0 0 0 0 0
Вывод:
0
Пример 3:
Ввод:
1 3
1 1 1
Вывод:
5
