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.

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².

Ivan and Powers of Two

Examples