題目描述

給定一個長度為N的初始序列 A[1], A[2], ..., A[N]，設初始的花費(cost)為0。

接著對這個序列進行恰好 N - 1 次操作，每次操作如下：

1. 任意選擇一個正整數 i ，且 i 小於目前序列的長度。
2. 花費 ( A[i] x A[i+1] )，將相鄰的兩個數 A[i] 與 A[i+1] 合併為 ( A[i] + A[i+1] - 1 )。
3. 對 A 的每一項重新編號，把剩下的數中最左邊的數作為 A[1]，接著作為 A[2]，A[3]，...，直到最右為止。( 每次 A 的長度減 1 )

總花費則定義為每次花費(cost)的總和。

在進行恰好 N - 1 次操作後，數列中將會只剩下一個數。

舉例來說，如果原本的數列是 1, 2, 3, 4，若選擇 i = 2，那麼在經過一次消去後會得到 1, 4, 4 (花費 2 x 3 = 6 )，再操作一次時選擇 i = 1，操作完畢後為 4, 4 (花費 1 x 4 = 4 )，再操作一次時選擇 i = 1，最後只剩下一個數 7 (花費 4 x 4 = 16 ) 並且結束操作，總花費是 6 + 4 + 16 = 26。

但是如果三次操作均選擇 i = 1，那麼總花費是 2 + 6 + 16 = 24，這是最小的總花費。

給定初始序列 A，請問在進行完所有操作後，總花費最低是多少呢？

輸入格式

輸入的第一列為一個整數N，介於1與2000之間。

輸入的第二列共有N個正整數，以一個空白隔開，依序表示初始序列 A[1], A[2], ..., A[N]。

輸出格式

請輸出一列，為一個整數，表示總花費的最小值。( 請注意：答案可能超過 2³² )

Samples

["1\r\n100","2\r\n100 100","3\r\n15 16 17","4\r\n10 10 10 10","4\r\n51 13 23 47","4\r\n1 2 3 4"]

["0","10000","750","561","6075","24"]

提示

初始序列 A 的最大值不超過 10000，但操作後可能超過 10000。

對於 N 不超過 20 的情況正確者，可得 5 分。

對於 N 不超過 100 的情況正確者，可再得 10 分。

原始資料

• Zero1 題號：a513
• Hydro 題號：Z0513
• Locale：zh_TW
• Display：practice