265B.md (1433B)
1 Source: https://codeforces.com/problemset/problem/265/B 2 3 B. Roadside Trees (Simplified Edition) 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 stdin 16 17 output 18 19 stdout 20 21 Squirrel Liss loves nuts. There are *n* trees (numbered 1 to *n* from west to east) along a street and there is a delicious nut on the top of each tree. The height of the tree *i* is *h**i*. Liss wants to eat all nuts. 22 23 Now Liss is on the root of the tree with the number 1. In one second Liss can perform one of the following actions: 24 25 * Walk up or down one unit on a tree. 26 * Eat a nut on the top of the current tree. 27 * Jump to the next tree. In this action the height of Liss doesn't change. More formally, when Liss is at height *h* of the tree *i* (1 ≤ *i* ≤ *n* - 1), she jumps to height *h* of the tree *i* + 1. This action can't be performed if *h* > *h**i* + 1. 28 29 Compute the minimal time (in seconds) required to eat all nuts. 30 31 Input 32 33 The first line contains an integer *n* (1 ≤ *n* ≤ 105) — the number of trees. 34 35 Next *n* lines contains the height of trees: *i*-th line contains an integer *h**i* (1 ≤ *h**i* ≤ 104) — the height of the tree with the number *i*. 36 37 Output 38 39 Print a single integer — the minimal time required to eat all nuts in seconds. 40 41 Examples 42 43 Input 44 45 ``` 46 2 47 1 48 2 49 ``` 50 51 Output 52 53 ``` 54 5 55 ``` 56 57 Input 58 59 ``` 60 5 61 2 62 1 63 2 64 1 65 1 66 ``` 67 68 Output 69 70 ``` 71 14 72 ```