codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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].