Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Want to solve the contest problems after the official contest ends? Just register for practice and you will be able to submit solutions.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Little Elephant and Sorting

time limit per test

0.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe Little Elephant loves sortings.

He has an array *a* consisting of *n* integers. Let's number the array elements from 1 to *n*, then the *i*-th element will be denoted as *a* _{ i}. The Little Elephant can make one move to choose an arbitrary pair of integers *l* and *r* (1 ≤ *l* ≤ *r* ≤ *n*) and increase *a* _{ i} by 1 for all *i* such that *l* ≤ *i* ≤ *r*.

Help the Little Elephant find the minimum number of moves he needs to convert array *a* to an arbitrary array sorted in the non-decreasing order. Array *a*, consisting of *n* elements, is sorted in the non-decreasing order if for any *i* (1 ≤ *i* < *n*) *a* _{ i} ≤ *a* _{ i + 1} holds.

Input

The first line contains a single integer *n* (1 ≤ *n* ≤ 10^{5}) — the size of array *a*. The next line contains *n* integers, separated by single spaces — array *a* (1 ≤ *a* _{ i} ≤ 10^{9}). The array elements are listed in the line in the order of their index's increasing.

Output

In a single line print a single integer — the answer to the problem.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

3

1 2 3

Output

0

Input

3

3 2 1

Output

2

Input

4

7 4 1 47

Output

6

Note

In the first sample the array is already sorted in the non-decreasing order, so the answer is 0.

In the second sample you need to perform two operations: first increase numbers from second to third (after that the array will be: [3, 3, 2]), and second increase only the last element (the array will be: [3, 3, 3]).

In the third sample you should make at least 6 steps. The possible sequence of the operations is: (2; 3), (2; 3), (2; 3), (3; 3), (3; 3), (3; 3). After that the array converts to [7, 7, 7, 47].

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/15/2020 22:25:38 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|