Problem Description

$ A $ slimes are lined up in a row. Initially, the size of each slime is $ 1 $.

Snuke can repeatedly perform the following operation:

• Choose a positive even number $ M $. Select $ M $ consecutive slimes and pair them as follows: the $(1,\ 2)$ th, $(3,\ 4)$ th, ..., $(M\ -\ 1,\ M)$ th slimes from the left. Then, merge each pair into one slime. The size of the resulting slime is the sum of the sizes of the slimes before merging. The order of the $M\ /\ 2$ slimes after merging remains the same as the order of the $M\ /\ 2$ pairs before merging.

Snuke's goal is to reduce the number of slimes to exactly $ N $ and make the size of the $ i $ th ($1\ <\ =\ i\ <\ =\ N$) slime from the left exactly $ a_i $. Find the minimum number of operations required for Snuke to achieve his goal.

Note that $ A $ is not given as input, and it is assumed that $A\ =\ a_1\ +\ a_2\ +\ ...\ +\ a_N$.

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $

Output Format

Output the minimum number of operations required for Snuke to achieve his goal.

Sample Input and Output

Sample Input #1

2
3 3

Sample Output #1

2

Sample Input #2

4
2 1 2 2

Sample Output #2

2

Sample Input #3

1
1

Sample Output #3

0

Sample Input #4

10
3 1 4 1 5 9 2 6 5 3

Sample Output #4

10

Notes/Hints

Constraints

• $1\ <\ =\ N\ <\ =\ 10^5$
• $ a_i $ is an integer.
• $1\ <\ =\ a_i\ <\ =\ 10^9$

Sample Explanation 1

The following operations can be performed: The slimes targeted for operation are shown in bold. - (1, **1**, **1**, **1**, **1**, 1) → (1, **2**, **2**, 1) - (**1**, **2**, **2**, **1**) → (**3**, **3**)

Sample Explanation 2

The following operations can be performed: - (**1**, **1**, 1, 1, 1, 1, 1) → (**2**, 1, 1, 1, 1, 1) - (2, 1, **1**, **1**, **1**, **1**) → (2, 1, **2**, **2**)

见题面 Input 部分

见题面 Output 部分