305C.md (1295B)
1 Source: https://codeforces.com/problemset/problem/305/C 2 3 C. Ivan and Powers of Two 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 Ivan has got an array of *n* non-negative integers *a*1, *a*2, ..., *a**n*. Ivan knows that the array is sorted in the non-decreasing order. 22 23 Ivan wrote out integers 2*a*1, 2*a*2, ..., 2*a**n* on a piece of paper. Now he wonders, what minimum number of integers of form 2*b* (*b* ≥ 0) need to be added to the piece of paper so that the sum of all integers written on the paper equalled 2*v* - 1 for some integer *v* (*v* ≥ 0). 24 25 Help Ivan, find the required quantity of numbers. 26 27 Input 28 29 The first line contains integer *n* (1 ≤ *n* ≤ 105). The second input line contains *n* space-separated integers *a*1, *a*2, ..., *a**n* (0 ≤ *a**i* ≤ 2·109). It is guaranteed that *a*1 ≤ *a*2 ≤ ... ≤ *a**n*. 30 31 Output 32 33 Print a single integer — the answer to the problem. 34 35 Examples 36 37 Input 38 39 ``` 40 4 41 0 1 1 1 42 ``` 43 44 Output 45 46 ``` 47 0 48 ``` 49 50 Input 51 52 ``` 53 1 54 3 55 ``` 56 57 Output 58 59 ``` 60 3 61 ``` 62 63 Note 64 65 In the first sample you do not need to add anything, the sum of numbers already equals 23 - 1 = 7. 66 67 In the second sample you need to add numbers 20, 21, 22.