1139B.md (1620B)
1 Source: https://codeforces.com/problemset/problem/1139/B 2 3 B. Chocolates 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You went to the store, selling $n$ types of chocolates. There are $a_i$ chocolates of type $i$ in stock. 22 23 You have unlimited amount of cash (so you are not restricted by any prices) and want to buy as many chocolates as possible. However if you buy $x_i$ chocolates of type $i$ (clearly, $0 \le x_i \le a_i$), then for all $1 \le j \lt i$ at least one of the following must hold: 24 25 * $x_j = 0$ (you bought zero chocolates of type $j$) 26 * $x_j \lt x_i$ (you bought less chocolates of type $j$ than of type $i$) 27 28 For example, the array $x = [0, 0, 1, 2, 10]$ satisfies the requirement above (assuming that all $a_i \ge x_i$), while arrays $x = [0, 1, 0]$, $x = [5, 5]$ and $x = [3, 2]$ don't. 29 30 Calculate the maximum number of chocolates you can buy. 31 32 Input 33 34 The first line contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$), denoting the number of types of chocolate. 35 36 The next line contains $n$ integers $a_i$ ($1 \le a_i \le 10^9$), denoting the number of chocolates of each type. 37 38 Output 39 40 Print the maximum number of chocolates you can buy. 41 42 Examples 43 44 Input 45 46 ``` 47 5 48 1 2 1 3 6 49 ``` 50 51 Output 52 53 ``` 54 10 55 ``` 56 57 Input 58 59 ``` 60 5 61 3 2 5 4 10 62 ``` 63 64 Output 65 66 ``` 67 20 68 ``` 69 70 Input 71 72 ``` 73 4 74 1 1 1 1 75 ``` 76 77 Output 78 79 ``` 80 1 81 ``` 82 83 Note 84 85 In the first example, it is optimal to buy: $0 + 0 + 1 + 3 + 6$ chocolates. 86 87 In the second example, it is optimal to buy: $1 + 2 + 3 + 4 + 10$ chocolates. 88 89 In the third example, it is optimal to buy: $0 + 0 + 0 + 1$ chocolates.