codeforces-scrape

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

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.