E - Doubling
配点 : 500 点
問題文
ハチロクさんは長さ N の数列 A を持っており、操作が不可能となるまで以下の操作を上から順に行うことを繰り返します。
- 1≤l≤r≤N 、r−l≥2、min (Al,Al+1,…,Ar)≥1 を全て満たす整数の組 (l,r) を選ぶ。そのような (l,r) が存在しない場合、操作を終了する。
- l<m<r を満たす整数 m を選ぶ。a=max (Am−1,Am+1), b=min (Am−1,Am+1) として、ハチロクさんは a mod b 円を受け取る。
ただし、x mod y は x を y で割った余りとする。
- Am を 0 で置き換える。
- 以下のどちらかを行う。
- 全ての 1≤i<m に対して、 min (Ai,Ai+1,…,Am−1)≥1 ならば Ai を Ai+Ai で置き換える。
- 全ての m<i≤N に対して、 min (Am+1,Am+2,…,Ai)≥1 ならば Ai を Ai+Ai で置き換える。
最適に行動した場合、ハチロクさんは最大で合計何円受け取ることが出来るでしょうか?
なお、この問題の制約下で操作が必ず有限回で終了することが証明できます。
制約
- 3≤N≤60
- 1≤Ai≤109
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
出力
答えを出力してください。
入力例1
出力例1
例えば、以下のような操作が最適であり、ハチロクさんは合計で 10 円受け取ることが出来ます。
- (l,r) として (1,3) を、 m として 2 を選び、 10 mod 8=2 円を受け取る。
- A2 を 0 で置き換える。A=(8,0,10,1,6) となる。
- A3,A4,A5 をそれぞれ 20,2,12 で置き換える。A=(8,0,20,2,12) となる。
- (l,r) として (3,5) を、 m として 4 を選び、 20 mod 12=8 円を受け取る。
- A4 を 0 で置き換える。A=(8,0,20,0,12) となる。
- A3 を 40 で置き換える。A=(8,0,40,0,12) となる。
- これ以上操作を行うことが出来ないので、操作を終了する。
入力例2
出力例2
入力例3
16
875 93706902 901274 2896 97359 907068 217463 380690 8745 9437689 67214 932759 2617 9034869 78236 2164712
出力例3