有 N 顆能量石頭排成一排，其能量分別是 X[1], X[2], ..., X[N]，現在每次可以挑一顆能量石，把它消去。消去第 i 顆石頭之後可以獲得相鄰兩個石頭的能量乘積 X[i-1]*X[i+1]，然後再併起來重新編號。如果一個石頭已經在最邊邊了，就不能消掉它。問最多可以獲得多少能量？
輸入的第一行有一個整數 T (1<=T<=1000) 表示有幾組測資。
對於每一組測試資料，第一行有一個正整數 N (1<=N<=50)，接下來有 N 個整數 X[1], X[2], ..., X[N]。(-1000<=X[i]<=1000)。
對於每一筆測試資料，請輸出能夠獲得的最大能量。
3 2 1 -2 4 1 2 3 4 5 100 2 1 3 100
0 12 10400
Migrated from old NTUJ.
topcoder
| No. | Testdata Range | Score |
|---|