← 返回题目列表

AtCoder · code_festival_2017_quala_f

F. 挤压史莱姆

中文机器翻译题面 查看原题

分数: 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