Problem Description

On this day, Xiaoming is cutting bamboo. In front of him there are $n$ bamboo plants in a row. At the beginning, the height of the $i$-th bamboo plant is $h_i$.

He feels that cutting them one by one is too slow, so he decides to use magic to cut the bamboo. The magic can be used on a consecutive segment of bamboo plants that all have the same height. Suppose the height of this segment is $H$. Then using the magic once can change the heights of all bamboo plants in this segment to $\left\lfloor\sqrt{\left\lfloor\frac{H}{2}\right\rfloor+1}\right\rfloor$, where $\lfloor x\rfloor$ means rounding $x$ down.

Xiaoming wants to know the minimum number of times he needs to use magic to make the heights of all bamboo plants become $1$.

Input Format

The first line contains a positive integer $n$, representing the number of bamboo plants.

The second line contains $n$ positive integers $h_i$ separated by spaces, representing the height of each bamboo plant.

Output Format

Output one integer, the answer.

6
2 1 4 2 6 7

5

Hint

Sample Explanation.

One possible plan:

$214267\rightarrow 214262\rightarrow 214222\rightarrow 211222\rightarrow 111222\rightarrow 111111$

A total of 5 steps are needed.

Constraints.

For $20\%$ of the testdata, it is guaranteed that $n \leq 1000$ and $h_i \leq 10^6$.

For $100\%$ of the testdata, it is guaranteed that $n \leq 2 \times 10^5$ and $h_i \leq 10^{18}$.

Lanqiao Cup 2022 Provincial Contest B Group, Problem J.

Translated by ChatGPT 5