460. Сила искусства

Не решаласьЛёгкая

Семён пишет аналитические статьи для искусствоведческого журнала. В своих работах он постоянно сталкивается с фундаментальными вопросами: «Что такое искусство?», «Как искусство влияет на людей?».

За годы работы в творческой среде Семён выработал собственные закономерности влияния произведения искусства на общественные тенденции. Он может сказать, влиятельно оно или нет, вне зависимости от количества критериев оценки влияния.

Принцип Семёна таков. Для произвольного объекта искусства определяется некоторое количество критериев в определённом порядке для оценки влияния. По каждому критерию можно набрать максимум nn первичных баллов. Вторичные баллы за условный критерий ii определяются следующим образом:

  • Если при оценке критерия набирается aia_i первичных баллов, то Семён начисляет критерию ai2a^2_i вторичных баллов.
  • Кроме того, Семён прибавляет бонусные баллы за aia_i следующих ненулевых оценок по другим критериям (прибавляются первичные баллы).
  • Для последнего критерия дополнительные баллы не начисляются.

Например, если n=10n=10, Семён оценивал произведение по пяти критериям и оно набрало [10,0,1,0,3][10, 0, 1, 0, 3] первичных баллов соответственно, то его итоговый результат будет равен 117117 вторичным баллам, так как за первый критерий он получил 102+1+310^2 + 1 + 3 балла, за второе и четвёртое — по 00, за третье — 12+31^2+3, за пятое — 323^2.

Семён дал последовательность результатов mm оценок критериев влиятельности произведения искусства. Определите общую сумму вторичных баллов.

Формат ввода

В первой строке даны два целых числа nn и mm (1n,m2000001 \le n, m \le 200\,000).

Во второй строке заданы mm целых чисел aia_i (0ain0 \le a_i \le n).

Формат вывода

Выведите сумму набранных баллов.

Примечание

Пример 3

  • Рассмотрим первый критерий: вторичных баллов за него: 121^2, то есть 11. Бонусные баллы начисляются за aia_i = 11 ненулевых оценок. Следующие 1 (то есть aia_i) ненулевых критериев имеют 1 первичный балл. Таким образом, за текущий критерий получаем 12+1=21^2 + 1 = 2 балла.

  • Второй критерий: аналогично с первым критерием. Итого получаем 12+1=21^2 + 1 = 2 за второй критерий.

  • Третий критерий: вторичных баллов 121^2, следующих критериев нет, поэтому баллов за третий критерий = 12=11^2 = 1.

Таким образом, сумма = (12+1)+(12+1)+12=5(1^2 + 1) + (1^2 + 1) + 1^2 = 5.

Ограничения

Ограничение времени

3 с

Ограничение памяти

256 МБ

Пример 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

Теги

Нужно войти, чтобы отправить решение.Войти