Squeezing Slimes
题意翻译
有一个长度为$A$的序列,最初序列的每个位置都是$1$
suneke君每次操作如下:
- 选一个正偶数$M$,从序列中选择长度为$M$的连续一段,从左往右编号为$(1, 2), (3, 4), \dots (M-1, M)$,相邻两个数为一对,一共$M/2$对数,每队数合成为一个数,合成后的数是合成前的两个数之和
给定一个长度为$N$的序列$a_1, a_2,\dots , a_N$,问suneke君至少要操作多少次才能将初始序列变为给定序列
```
有一个长度为$A$的序列,最初序列的每个位置都是$1$
suneke君每次操作如下:
- 选一个正偶数$M$,从序列中选择长度为$M$的连续一段,从左往右编号为$(1, 2), (3, 4), \dots (M-1, M)$,相邻两个数为一对,一共$M/2$对数,每队数合成为一个数,合成后的数是合成前的两个数之和
给定一个长度为$N$的序列$a_1, a_2,\dots , a_N$,问suneke君至少要操作多少次才能将初始序列变为给定序列
```
题目描述
[problemUrl]: https://atcoder.jp/contests/code-festival-2017-quala/tasks/code_festival_2017_quala_f
$ 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 $ であるとします。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $
输出格式
すぬけ君が目標を達成するために必要な操作回数の最小値を出力せよ。
输入输出样例
输入样例 #1
2
3 3
输出样例 #1
2
输入样例 #2
4
2 1 2 2
输出样例 #2
2
输入样例 #3
1
1
输出样例 #3
0
输入样例 #4
10
3 1 4 1 5 9 2 6 5 3
输出样例 #4
10
说明
### 制約
- $ 1\ <\ =\ N\ <\ =\ 10^5 $
- $ a_i $ は整数である。
- $ 1\ <\ =\ a_i\ <\ =\ 10^9 $
### Sample Explanation 1
次のように操作を行えばよいです。 操作対象のスライムを太字で表しています。 - (1, \*\*1\*\*, \*\*1\*\*, \*\*1\*\*, \*\*1\*\*, 1) → (1, \*\*2\*\*, \*\*2\*\*, 1) - (\*\*1\*\*, \*\*2\*\*, \*\*2\*\*, \*\*1\*\*) → (\*\*3\*\*, \*\*3\*\*)
### Sample Explanation 2
次のように操作を行えばよいです。 - (\*\*1\*\*, \*\*1\*\*, 1, 1, 1, 1, 1) → (\*\*2\*\*, 1, 1, 1, 1, 1) - (2, 1, \*\*1\*\*, \*\*1\*\*, \*\*1\*\*, \*\*1\*\*) → (2, 1, \*\*2\*\*, \*\*2\*\*)