行列の積

n 個の行列 が与えられており、それぞれのサイズは です。行列は左から右へ 1 から n の順に並んでいて、どのように括弧を配置して掛け合わせるかは自由に決められます。

すべての行列を掛け合わせるために必要な演算回数の最小値を求めてください。

入力

最初の行には整数 n () が 1 つ与えられます。

続く n 行には、それぞれの行列の次元 (1 ≤ ≤ 1000) が与えられます。

また、 に対して が保証されています。

出力

すべての行列を掛け合わせるのに必要な演算の最小回数を出力してください。

例