Problem3448--Ivan and Powers of Two

3448: Ivan and Powers of Two

[Creator : ]
Time Limit : 2.000 sec  Memory Limit : 256 MiB

SubmitSolved: 0Submit Num: 0StatisticsShowOff!

Description

time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ivan has got an array of n non-negative integers a1,a2,...,an. Ivan knows that the array is sorted in the non-decreasing order.

Ivan wrote out integers 2a1,2a2,...,2an on a piece of paper. Now he wonders, what minimum number of integers of form 2b (b≥0) need to be added to the piece of paper so that the sum of all integers written on the paper equalled 2v-1 for some integer v (v≥0).

Help Ivan, find the required quantity of numbers.

Input

The first line contains integer n (1≤n≤105). The second input line contains n space-separated integers a1,a2,...,an (0≤ai≤2·109). It is guaranteed that a1≤a2≤...≤an.

Output

Print a single integer − the answer to the problem.

Examples
Input
4
0 1 1 1
Output
0
Input
1
3
Output
3
Note

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

In the second sample you need to add numbers 20,21,22.

Source/Category

 
Submit