\(N\)개의 풍선이 일렬로 있고, \(i\)번째 풍선에는 수 \(a_i\)가 적혀 있다. 풍선을 하나씩 터뜨린다. 풍선 \(i\)를 터뜨리면 \(L \cdot a_i \cdot R\) 만큼의 동전을 얻는데, 여기서 \(L\)과 \(R\)은 아직 터지지 않은, \(i\)의 바로 왼쪽과 오른쪽에 있는 풍선의 수이다(양 끝 바깥의 없는 이웃은 \(1\)로 간주한다). 모든 풍선을 최적의 순서로 터뜨려 얻을 수 있는 최대 동전 수를 구하시오.

첫 줄에 \(N\) (\(1 \le N \le 60\))이 주어진다. 둘째 줄에 \(N\)개의 정수 \(a_i\) (\(0 \le a_i \le 100\))가 주어진다.

최대 동전 수를 출력한다.

riseoj 작성

출처 RiseOJ Basics