Statistics

Interview

Time limit2sMemory limit512 MB

Summary

Given daily case counts, reduce each value (never increase) so the sequence becomes non-increasing, minimizing the total amount removed.

Level: Medium4 of 10
Topics: Greedy, Array, Implementation
Solved: No attempts yet

Problem

Coronavirus cases are now rising very fast in Neverland. The rise is mainly caused by a new variant of the virus which spreads more rapidly than the original version. People are frustrated by seeing another spike in the statistics, and at the same time there is no clear estimate of when vaccination will be available in the country.

Although the new variant of coronavirus is not believed to be more deadly, the rise in the new case statistics has made people panicked and afraid. Therefore, the government of Neverland has decided to manipulate the new case statistics slightly to reduce people's anxiety. The goal of the manipulation is to show that the new cases are not rising in the coming few days. More precisely, the number of new cases announced on each of the coming days must be equal to or lower than the number announced on its preceding day. Due to investigations, the only way to change the statistics is to throw away some test results. Therefore, the announced numbers must always be less than or equal to the real numbers.

As the manipulation is not free, the government is going to hire a computer scientist to calculate the minimum total amount by which the real numbers must be changed in order to achieve the above goal. Because of your experience in the ICPC programming contests, the government has selected you for this critical mission.

Input

The first line of the input consists of $n$ ( $1 \le n \le 10\,000$ ), the number of the coming days. Each of the next $n$ lines contains an integer $p_i$ ( $0 \le p_i \le 1000$ ), indicating the real number of new cases on the $i$ -th day.

Output

Print the minimum total amount by which the real numbers must be changed in order for the new cases not to be rising in the coming days.

Examples3

Example 1
Input
```
3
100
150
200
```
Expected output
```
150
```
Example 2
Input
```
2
5
4
```
Expected output
```
0
```
Example 3
Input
```
4
10
0
9
8
```
Expected output
```
17
```