Codeforces Round 184 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

greedy

implementation

*1600

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Ivan and Powers of Two

time limit per test

0.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIvan 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.

Ivan wrote out integers 2^{a1}, 2^{a2}, ..., 2^{an} 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^{5}). The second input line contains *n* space-separated integers *a*_{1}, *a*_{2}, ..., *a*_{n} (0 ≤ *a*_{i} ≤ 2·10^{9}). It is guaranteed that *a*_{1} ≤ *a*_{2} ≤ ... ≤ *a*_{n}.

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 2^{3} - 1 = 7.

In the second sample you need to add numbers 2^{0}, 2^{1}, 2^{2}.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/20/2024 13:23:19 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|