E - Doubling

配点 : 500500
  

問題文

ハチロクさんは長さ NN の数列 AA を持っており、操作が不可能となるまで以下の操作を上から順に行うことを繰り返します。
 

  • 1lrN1 \leq l \leq r \leq Nrl2r-l \geq 2min\rm{min} (Al,Al+1,,Ar)1(A_l,A_{l+1},\ldots,A_r) \geq 1 を全て満たす整数の組 (l,r)(l,r) を選ぶ。そのような (l,r)(l,r) が存在しない場合、操作を終了する。
  • l<m<rl < m < r を満たす整数 mm を選ぶ。a=maxa=\rm{max} (Am1,Am+1), b=min(A_{m-1},A_{m+1}),\ b=\rm{min} (Am1,Am+1)(A_{m-1},A_{m+1}) として、ハチロクさんは aa mod\rm{mod} bb 円を受け取る。
    ただし、xx mod\rm{mod} yyxxyy で割った余りとする。
  • AmA_m00 で置き換える。
  • 以下のどちらかを行う。
    • 全ての 1i<m1 \leq i <m に対して、 min\rm{min} (Ai,Ai+1,,Am1)1(A_i,A_{i+1},\ldots,A_{m-1}) \geq 1 ならば AiA_iAi+AiA_i+A_i で置き換える。
    • 全ての m<iNm< i \leq N に対して、 min\rm{min} (Am+1,Am+2,,Ai)1(A_{m+1},A_{m+2},\ldots,A_i) \geq 1 ならば AiA_iAi+AiA_i+A_i で置き換える。

 
最適に行動した場合、ハチロクさんは最大で合計何円受け取ることが出来るでしょうか?
なお、この問題の制約下で操作が必ず有限回で終了することが証明できます。

  

制約

  • 3N603\leq N \leq 60
  • 1Ai1091\leq A_i \leq 10^9
  • 入力は全て整数

  

入力

入力は以下の形式で標準入力から与えられます。

NN
A1 A2  ANA_1 \ A_2 \ \ldots \ A_N

  

出力

答えを出力してください。

  

入力例1

5
8 90 10 1 6

出力例1

10

例えば、以下のような操作が最適であり、ハチロクさんは合計で 1010 円受け取ることが出来ます。

  • (l,r)(l,r) として (1,3)(1,3) を、 mm として 22 を選び、 1010 mod\rm{mod} 8=28 =2 円を受け取る。
  • A2A_200 で置き換える。A=(8,0,10,1,6)A=(8,0,10,1,6) となる。
  • A3,A4,A5A_3,A_4,A_5 をそれぞれ 20,2,1220,2,12 で置き換える。A=(8,0,20,2,12)A=(8,0,20,2,12) となる。
  • (l,r)(l,r) として (3,5)(3,5) を、 mm として 44 を選び、 2020 mod\rm{mod} 12=812 =8 円を受け取る。
  • A4A_400 で置き換える。A=(8,0,20,0,12)A=(8,0,20,0,12) となる。
  • A3A_34040 で置き換える。A=(8,0,40,0,12)A=(8,0,40,0,12) となる。
  • これ以上操作を行うことが出来ないので、操作を終了する。  
     

入力例2

7
17 3 33 7 131 54 523

出力例2

600

 
 

入力例3

16
875 93706902 901274 2896 97359 907068 217463 380690 8745 9437689 67214 932759 2617 9034869 78236 2164712

出力例3

57798582

Submit


Go (1.21)