问题描述

伊凡在纸上写下了一个由 n 个非负整数组成的序列 $a_1$，$a_2$ ，…，$a_n$ 。这个序列保证单调不降。 接着，伊凡又在纸上写下了另一个序列 2^a1, 2^a2, ，…，2^an 。现在他想知道，最少要在这个序列中添加多少个形式为 2^x 的数（x 为非负整数），才能使这个序列所有整数的和为 2^v-1 ，其中 v 为某个非负整数。

Format

Input

第 1 行包括 1 个正整数 n（1≤n≤<10⁵ ）。 第 2 行包括 n 个由空格隔开的整数$a_1$，$a_2$ ，…，$a_n$ 。其中，0≤ai ≤2×10⁵ ，保证 $a_1$ ≤$a_2$ ≤…≤$a_n$ 。

Output

输出一行一个整数，表示最少在序列中添加数的数量。

Samples

4
0 1 1 1

0

在第1个样例中不需要添加任何数， 因为2⁰+2¹+ 2¹+ 2¹ =1+2+2+2=7=2³-1。

1
3

3

在第2个样例中，需要至少添加 3 个数，分别为2⁰，2¹，2²

Limitation

1s, 1024KiB for each test case.