Fresas con crema

Ya casi habían terminado de ayudar a reorganizar el ala de Patologías Psicológicas cuando Felipe finalmente descubrió que Charly había pasado buena parte de la misión leyendo expedientes en lugar de trabajar.

—¿Se puede saber qué estás haciendo? —preguntó Felipe.

—Investigación de campo —respondió Charly sin apartar la vista de los archivos.

—Eso no es investigación de campo.

—Investigación de escritorio, entonces.

Mientras el resto de la tripulación se preparaba para continuar su recorrido por MANDRÁGORA-88b, Charly alcanzó a tomar un último expediente de uno de los archivadores automáticos.

—Uno más y nos vamos —prometió.

El archivo provenía de principios del siglo XXI y estaba clasificado dentro de la categoría de Fenómenos Culturales Inexplicablemente Populares.

En un documento se narraba que durante la década de 2020 existió un alimento extremadamente popular conocido como fresas con crema.

Fig 1. Fresas con crema

Aparentemente habia sido un alimento tan popular que llego a ser considerado un regalo sagrado

Habia un expediente que relataba un problema que sucedio por culpa de las fresas con crema:

Sofía llevaba toda la noche planeando, junto a sus amigos, un problema que acabe con todos los competidores de la OMISLP. Aunque ella sabe que aún está lejos de su obra maestra (por lo cual mantendrá el problema en secreto por ahora), deseaba recompensar a todos los amigos que la apoyaron con la planeación.

A lo largo de la noche, cada amigo fue aportando ideas y Sofía guardó este registro: el amigo \(i\) aportó \(A_i\) ideas. Como Sofía es muy analítica, está consciente de que la gente con muchas ideas aportadas ya está bastante satisfecha consigo misma por su gran intelecto. Sin embargo, desea ser justa y agradecida, por lo que decidió regalarle a cada uno de sus amigos un buen vaso lleno de crema.

Pero un vaso de crema no es nada sin su ingrediente principal. Para repartir las fresas, Sofía inventó una regla: para todo par de amigos distintos \(i\) y \(j\), si el amigo \(i\) aportó más ideas que el amigo \(j\) (\(A_i \geq A_j\)), entonces Sofía le regala al amigo \(i\) exactamente \(A_i - A_j\) fresas para su vaso.

Tu tarea es ayudar a Sofía a determinar la cantidad total de fresas que tiene que comprar en el súper para poder hacer la repartición exacta entre todos sus amigos.

Entrada

La primera línea contiene un número entero \(N\), la cantidad de amigos que ayudaron a Sofía.

La segunda línea contiene \(N\) enteros \(A_1, A_2, \dots, A_N\) separados por un espacio, que representan la cantidad de ideas que aportó cada amigo.

Salida

Imprime un único número: la cantidad total de fresas que Sofía necesita comprar.

Nota importante: La respuesta puede ser un número gigantesco que exceda el límite de un entero de 32 bits. Asegúrate de usar tipos de datos enteros de 64 bits (long long en C++).

Ejemplos

Ejemplo 1

Entrada

5
1 2 3 4 5

Salida

20

Ejemplo 2

Entrada

10
0 0 0 0 0 10000000 0 0 0 0

Salida

90000000

Nota

En el Ejemplo 1, la repartición de fresas ocurre de la siguiente manera:

• El primer amigo no recibe fresas de nadie, porque nadie aportó menos ideas que él.
• El segundo amigo recibe 1 fresa (por ganarle al primer amigo).
• El tercer amigo recibe 3 fresas (2 de ganarle al primero, y 1 de ganarle al segundo).
• El cuarto amigo recibe 6 fresas (3+2+1).
• El quinto amigo recibe 10 fresas (4+3+2+1). En total, Sofía debe comprar 20 fresas.

Límites

• \(1 \le N \le 2 \cdot 10^5\)
• \(0 \le A_i \le 10^9\)

Detalles de Implementación

• Cada par de amigos se evalúa de forma independiente.
• Un mismo amigo puede recibir fresas por superar a múltiples personas. Todo se va acumulando en su vaso de crema.

Subtareas

• Subtarea 1 [15 puntos]: \(1 \leq N \leq 1000\).
• Subtarea 2 [5 puntos]: Todos los valores de \(A_i\) son iguales.
• Subtarea 3 [5 puntos]: \(A\) es una permutación de los números del \(1\) al \(N\).
• Subtarea 4 [10 puntos]: Para cualquier \(i\), se cumple que \(0 \leq A_i \leq 1\).
• Subtarea 5 [15 puntos]: Para cualquier \(i\), se cumple que \(0 \leq A_i \leq 10^4\).
• Subtarea 6 [15 puntos]: Hay a lo sumo dos valores distintos en \(A\).
• Subtarea 7 [35 puntos]: Sin restricciones adicionales.