分数: 1600 点
问题陈述
有 A 史莱姆排成一排。 最初,史莱姆的大小都是 1.
Snuke可以重复执行以下操作。
- 选择一个正偶数 M。然后,选择 M 连续的史莱姆和形态 M / 2 与这些史莱姆配对如下:将 1-st 和 2- 其中从左起, 3-rd 和 4- 其中第一个, ..., (M-1)-th 和 M- 第一个。将每对史莱姆组合成一个更大的史莱姆。这里,组合史莱姆的大小是组合前各个史莱姆的总和。的顺序 M / 2 组合史莱姆与原史莱姆相同 M / 2 组合前的史莱姆对。
Snuke 想要达到这样的情况: N 史莱姆,以及尺寸 i-th (1 ≤ i ≤ N) 左边的史莱姆是 a_i。 找出实现他的目标所需的最少操作次数。
请注意 A 不直接作为输入给出。假设 A = a_1 + a_2 + ... + a_N.
约束
- 1 ≤ N ≤ 10^5
- a_i 是一个整数。
- 1 ≤ a_i ≤ 10^9
输入
输入由标准输入按以下格式给出:
N a_1 a_2 ... a_N
输出
打印实现 Snuke 目标所需的最少操作数。
示例输入 1
2 3 3
示例输出 1
2
实现 Snuke 目标的一种方法如下。 在这里,选定的史莱姆以粗体标记。
- (1, 1, 1, 1, 1, 1) → (1, 2, 2, 1)
- (1, 2, 2, 1) → (3, 3)
示例输入 2
4 2 1 2 2
示例输出 2
2
实现 Snuke 目标的一种方法如下。
- (1, 1, 1, 1, 1, 1, 1) → (2, 1, 1, 1, 1, 1)
- (2, 1, 1, 1, 1, 1) → (2, 1, 2, 2)
示例输入 3
1 1
示例输出 3
0
示例输入 4
10 3 1 4 1 5 9 2 6 5 3
示例输出 4
10