풍선 축제에서 일렬로 놓인 \(N\) 개의 풍선을 모두 터뜨리려 합니다. \(i\) 번째 풍선에는 점수 \(a_i\) 가 적혀 있습니다.

풍선 하나를 터뜨릴 때, 그 풍선의 점수와 현재 줄에서 바로 왼쪽·오른쪽에 남아 있는 풍선의 점수를 곱한 값을 얻습니다. 양 끝 바깥에는 점수 \(1\) 인 가상의 풍선이 있다고 봅니다. 즉 풍선 \(k\) 를 터뜨리면 \(L \times a_k \times R\) 점을 얻고, 여기서 \(L\), \(R\) 은 현재 인접한 풍선의 점수(없으면 \(1\))입니다.

풍선을 터뜨리는 순서를 잘 정해서 얻을 수 있는 최대 총점을 구하세요.

\(1 \le N \le 300\), \(1 \le a_i \le 100\)

첫 줄에 풍선의 수 \(N\) 이 주어집니다. (\(1 \le N \le 300\))

둘째 줄에 \(N\) 개의 정수 \(a_1, \dots, a_N\) 이 주어집니다. (\(1 \le a_i \le 100\))

얻을 수 있는 최대 총점을 출력합니다.

riseoj 작성

출처 Original