【2022年省赛B组】试题J:砍竹子

问题描述

这天，小明在砍竹子，他面前有$n$棵竹子排成一排，一开始第$i$棵竹子的高度为$h_i$。 他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为$H$，那么用一次魔法可以把这一段竹子的高度都变为$\bigg \lfloor {\sqrt{ \big\lfloor \dfrac{H}{2} \big\rfloor+ 1 }} \bigg \rfloor$,其中$\lfloor x \rfloor$表示对$x$向下取整。小明想知道他最少使用多少次魔法可让所有的竹子的高度都为$1$。

输入格式

第一行为一个正整数$n$，表示竹子的棵数。 第二行共$n$个空格分开的正整数$h_i$，表示每棵竹子的高度。

输出格式

一个整数表示答案。

样例输入输出

6
2 1 4 2 6 7

5

样例说明

其中一种方案：

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

共需要5步完成。

评测用例规模与规定

对于$20\%$的评测样例,$n \leqslant 1000, h_i \leqslant 10^6$。

对于$100\%$的评测样例，$n \leqslant 2 \times 10^5, h_i \leqslant 10^{18}$。

运行限制

• 最大运行时间：$2s$
• 最大运行内存：$256M$