ACM 2014 - Round #3Ended |
F - Amplificación
Languages: C, C++, Java, JavaScript, Tiger, Python, Haskell, Pascal, 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
Notes
Hint
Caso 2:
