Автор задачи и разработчик: Даниил Голов
Рассмотрим случай, когда Даниил любит только одну какую-то песню. Тогда он послушает ее $$$k$$$ раз и получит удовольствие $$$a_1 + (a_1 - 1) + (a_i - 2) + \ldots$$$. Количество прослушиваний песни в плейлисте, когда она приносит хоть какое-то удовольствие, равно $$$t = \min(k, a_i)$$$. Поэтому ответом будет число $$$a_1 + (a_1 - 1) + \ldots + (a_1 - t + 1) = t \left(a_1 - \frac{t - 1}{2}\right)$$$.
Теперь рассмотрим случай, когда $$$n > 1$$$. Тогда всегда найдутся две песни, которые можно слушать по очереди и удовольствие от их прослушивания не будет уменьшаться. Выберем две песни с наибольшими $$$a_i$$$, пусть они, не теряя общности, имеют номера $$$1$$$ и $$$2$$$ и пусть $$$a_1 \geqslant a_2$$$. Рассматривать какие-то песни, кроме этих двух, не имеет смысла. Если Даниил каждый раз выбирает песню с максимальным на текущий момент $$$a_i$$$, то до песен с третьим и ниже по величине $$$a_i$$$ он никогда не дойдет.
Обозначим $$$d = a_1 - a_2$$$. Если $$$d = 0$$$, то есть $$$a_1 = a_2$$$, Даниил за каждое прослушивание будет получать ровно $$$a_1$$$ удовольствия, и ответ будет $$$n a_1$$$. Иначе, после $$$d$$$ прослушиваний первой песни, Даниил получит $$$a_1 + (a_1 - 1) + \ldots + (a_2 + 1)$$$ удовольствия, после чего один раз послушает вторую песню вместо первой. В итоге удовольствие от прослушивания первой песни примет свое изначальное значение $$$a_1$$$, и Даниил снова повторит этот цикл.
Таким образом, весь плейлист разбивается на одинаковые блоки по $$$d + 1$$$ песен, и, возможно, еще часть такого блока в конце. Суммарное удовольствие в блоке или в начале блока можно вычислить по формуле суммы арифметической прогрессии, поэтому асимптотика такого решения — $$$\mathcal{O}(1)$$$.