問題文


長さ の数列 が与えられます。 また、数列 の空でない部分列を とします。

ここで、 に対するスコア を以下のように定義します。

  • の長さが であるとき、

考えられる 通りありますが、そのうち の最大値を求めてください。

制約


  • 入力は全て整数

入力


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


出力


の最大値を出力せよ。

サンプル


サンプル1

入力
3
4 6 3
出力
6
  • のとき,
  • のとき,
  • のとき,
  • のとき,
  • のとき,
  • のとき,
  • のとき,

以上より, が正解です.

サンプル2

入力
7
12 6 4 7 8 6 16
出力
18

提出


Go (1.14)