P8787 [Lanqiao Cup 2022 NOI Qualifier B] Cutting Bamboo

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$.

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 one integer, the answer.

**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