La Conquête de l'Est – Regional event 2012

Level 3

Énoncé

Joseph Marchand est un trader. Il achète des biens pour les revendre plus cher. Aidez-le dans sa tâche pour maximiser ses profits.

Joseph arrive à prédire le prix de l'acier sur plusieurs jours. Il peut acheter 1 unité d'acier un jour et le revendre plus tard.

Entrée

L'entrée comprendra :

  • Le nombre de jour N où Joseph peut prédire le prix de l'acier.
  • Sur la seconde ligne, le prix Pi d'une unité d'acier au i-ème jour.

Sortie

Le gain maximal que Joseph peut faire en achetant puis vendant une seule unité d'acier durant la période proposée en entrée.

Contraintes

  • 1 <= N <= 100 000
  • 1 <= Pi <= 10 000

Runtime constraints

Maximum memory usage
1200 kilobytes
Maximum execution time
400 milliseconds

Input/output samples

Sample input
1
42
Sample output
0
Sample input
2
5 12
Sample output
7
Sample input
6
11 12 7 9 8 10
Sample output
3

Submit your solution

You have to register or log in to be able to submit your solution.