F - Amplificación

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

Usted tiene una secuencia de N (1 ≤ N ≤ 200000) números naturales Ai (1 ≤ i ≤ N, 1 ≤ Ai ≤ 10^9). Usted puede aplicarle algunas amplificaciones. Cada amplificación adiciona 1 a todos los números Ai para i en el rango de L a R (1 ≤ L ≤ R ≤ N). La amplificación puede usarse solo si todos los números Ai en el rango de L a R son iguales. Escriba un programa que calcule el mínimo número de amplificaciones necesarias para igualar los número de la secuencia completa Ai (1 ≤ i ≤ N).

Input

Línea 1 : Un entero N.
Línea 2 : N enteros Ai separados por espacio.

Output

Línea 1 : Un solo entero: el mínimo número de amplificaciones para hacer iguales a todos los números Ai.

Sample test(s)

Input
3 1 3 2
Output
3
Input
4 1 2 4 2
Output
5
Input
5 3 1 4 1 1
Output
6

Hints

Hint

Caso 2: