205B.md (2080B)
1 Source: https://codeforces.com/problemset/problem/205/B 2 3 B. Little Elephant and Sorting 4 5 time limit per test 6 7 0.5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 The Little Elephant loves sortings. 22 23 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*. 24 25 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. 26 27 Input 28 29 The first line contains a single integer *n* (1 ≤ *n* ≤ 105) — the size of array *a*. The next line contains *n* integers, separated by single spaces — array *a* (1 ≤ *a**i* ≤ 109). The array elements are listed in the line in the order of their index's increasing. 30 31 Output 32 33 In a single line print a single integer — the answer to the problem. 34 35 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. 36 37 Examples 38 39 Input 40 41 ``` 42 3 43 1 2 3 44 ``` 45 46 Output 47 48 ``` 49 0 50 ``` 51 52 Input 53 54 ``` 55 3 56 3 2 1 57 ``` 58 59 Output 60 61 ``` 62 2 63 ``` 64 65 Input 66 67 ``` 68 4 69 7 4 1 47 70 ``` 71 72 Output 73 74 ``` 75 6 76 ``` 77 78 Note 79 80 In the first sample the array is already sorted in the non-decreasing order, so the answer is 0. 81 82 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]). 83 84 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].