Ivan and Powers of Two

0ms

262144K

Description:

Ivan has got an array of n non-negative integers a₁, a₂, ..., a_n. Ivan knows that the array is sorted in the non-decreasing order.

Ivan wrote out integers 2^a₁, 2^a₂, ..., 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).

Help Ivan, find the required quantity of numbers.

Input:

The first line contains integer n (1 ≤ n ≤ 10⁵). The second input line contains n space-separated integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 2·10⁹). It is guaranteed that a₁ ≤ a₂ ≤ ... ≤ a_n.

Output:

Print a single integer — the answer to the problem.

Sample Input:

4
0 1 1 1

Sample Output:

Sample Input:

1
3

Sample Output:

Note:

In the first sample you do not need to add anything, the sum of numbers already equals 2³ - 1 = 7.

In the second sample you need to add numbers 2⁰, 2¹, 2².

Informação

Provedor Codeforces

Código CF305C