A - Clear The Context
Milk
2
s
1024
MB
150
点
問題文
yurufuwa AI は、会話履歴を保存しながら依頼に答える AI です。文章の長さは「トークン」という単位で表され、利用量もこの単位で数えます。
siro53 君は yurufuwa AI に $N$ 個の依頼を順番に送ります。最初、会話履歴の長さは $0$ トークンです。
各整数 $i$($1 \leq i \leq N$)について、$i$ 番目の依頼を送ると、次の処理が順に行われます。
- 会話履歴の長さが $A_i$ トークン増える。
- 会話履歴の長さと同じ数のトークンを消費する。
また、siro53 君は、次の操作を高々 $1$ 回行うことができます。
整数 $i$($1 \leq i \leq N$)を $1$ つ選ぶ。$i$ 番目の依頼の処理がすべて終了した直後に、会話履歴の長さを $0$ トークンにする。
この操作ではトークンを消費せず、それまでに消費したトークン数も減りません。操作後の依頼は、長さが $0$ トークンになった会話履歴を引き継いで処理します。
$N$ 個すべての依頼を送るまでに消費するトークン数の合計の最小値を求めてください。
制約
- $2 \leq N \leq 200$
- $1 \leq A_i \leq 10^5$($1 \leq i \leq N$)
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられます。
$N$
$A_1 \space A_2 \space \ldots \space A_N$
出力
$N$ 個すべての依頼を送るまでに消費するトークン数の合計の最小値を 1 行に出力してください。
入力例 1
5
3 1 4 1 5
出力例 1
22
$3$ 番目の依頼と $4$ 番目の依頼の間で会話履歴を $0$ にすると、各依頼で消費するトークン数は $3,4,8,1,6$ となり、合計は $22$ です。これが最小値となります。
入力例 2
4
100 1 1 1
出力例 2
106
$1$ 番目の依頼と $2$ 番目の依頼の間で会話履歴を $0$ にすると、各依頼で消費するトークン数は $100,1,2,3$ となり、合計は $106$ です。これが最小値となります。