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

The problem statement has recently been changed. View the changes.

×
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-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/30/2023 21:20:05 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|