/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1600 点
問題文
A 匹のスライムが横一列に並んでいます。 最初、スライムの大きさはすべて 1 です。
すぬけ君は次の操作を繰り返し行うことができます。
- 正の偶数 M をひとつ選ぶ。 位置が連続する M 匹のスライムを選び、それらのうち左から (1,\ 2) 番目、(3,\ 4) 番目、…、(M - 1,\ M) 番目のスライムをそれぞれペアにする。 そして、各ペアごとに 2 匹のスライムを合成して 1 匹のスライムにする。 ここで、合成後のスライムの大きさは、合成前のスライムの大きさの和とする。 また、合成後の M / 2 匹のスライムの順序は、合成前の M / 2 組のペアの順序のままである。
すぬけ君の目標は、スライムをちょうど N 匹にして、それらのうち左から i (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
出力
すぬけ君が目標を達成するために必要な操作回数の最小値を出力せよ。
入力例 1
2 3 3
出力例 1
2
次のように操作を行えばよいです。 操作対象のスライムを太字で表しています。
- (1, 1, 1, 1, 1, 1) → (1, 2, 2, 1)
- (1, 2, 2, 1) → (3, 3)
入力例 2
4 2 1 2 2
出力例 2
2
次のように操作を行えばよいです。
- (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
Score : 1600 points
Problem Statement
There are A slimes lining up in a row. Initially, the sizes of the slimes are all 1.
Snuke can repeatedly perform the following operation.
- Choose a positive even number M. Then, select M consecutive slimes and form M / 2 pairs from those slimes as follows: pair the 1-st and 2-nd of them from the left, the 3-rd and 4-th of them, ..., the (M-1)-th and M-th of them. Combine each pair of slimes into one larger slime. Here, the size of a combined slime is the sum of the individual slimes before combination. The order of the M / 2 combined slimes remain the same as the M / 2 pairs of slimes before combination.
Snuke wants to get to the situation where there are exactly N slimes, and the size of the i-th (1 ≤ i ≤ N) slime from the left is a_i. Find the minimum number of operations required to achieve his goal.
Note that A is not directly given as input. Assume A = a_1 + a_2 + ... + a_N.
Constraints
- 1 ≤ N ≤ 10^5
- a_i is an integer.
- 1 ≤ a_i ≤ 10^9
Input
Input is given from Standard Input in the following format:
N a_1 a_2 ... a_N
Output
Print the minimum number of operations required to achieve Snuke's goal.
Sample Input 1
2 3 3
Sample Output 1
2
One way to achieve Snuke's goal is as follows. Here, the selected slimes are marked in bold.
- (1, 1, 1, 1, 1, 1) → (1, 2, 2, 1)
- (1, 2, 2, 1) → (3, 3)
Sample Input 2
4 2 1 2 2
Sample Output 2
2
One way to achieve Snuke's goal is as follows.
- (1, 1, 1, 1, 1, 1, 1) → (2, 1, 1, 1, 1, 1)
- (2, 1, 1, 1, 1, 1) → (2, 1, 2, 2)
Sample Input 3
1 1
Sample Output 3
0
Sample Input 4
10 3 1 4 1 5 9 2 6 5 3
Sample Output 4
10