어느 추운 겨울날, 병천에 있는 한 작은 마을에 얼음이 꽁꽁 얼었습니다. 얼음을 없애고 싶은 당신은 한가지 묘수를 생각해 냅니다. 얼음을 깨는 일을 게임으로 만든 것이죠.

얼음은 일 열로 늘어서 있습니다. 이 얼음을 모두 깨면서 점수를 가장 많이 얻는 게 게임의 목표 입니다. 게임의 규칙은 간단합니다. 각각의 얼음마다 점수가 있습니다. 한 얼음을 깨면 붙어 있는 얼음들의 점수의 곱만큼의 점수를 얻을 수 있습니다 (만약 제일 끝에 있는 얼음이어서 옆에 얼음이 없다면 1을 곱합니다). 그리고 얼음이 깨졌으면 그 얼음은 사라지고 양옆에 있던 얼음이 서로 붙게 됩니다. 예를 들어서 얼음이 아래와 같이 이어져 있다면..

3, 1, 5, 8

처음에는 1을 깹니다. 이 때의 점수는 3 * 1 * 5 = 15 점이 됩니다. 점수가 1인 얼음이 깨졌으므로 다음 얼음의 배열은 아래와 같아집니다.

3, 5, 8

여기서 5를 깨면 점수 3 * 5 * 8 = 120 점을 얻게 됩니다. 그다음엔 3을 깨면 24점, 마지막으로 8을 깨면 8점을 얻어서 총 167점을 얻게 됩니다.

게임이면 학식도 거를 정도의 열심히 하는 그 학교 학생들은 모두 그 게임에 참가해서 가장 큰 점수를 내기 위해 서로만의 전략을 짜고 있습니다.

당신만의 전략으로 가장 높은 점수를 내주세요.

첫 줄에는 얼음의 개수 N (1 <= N <= 500) 이 주어집니다.

그 다음줄에는 각 얼음의 점수 i (1 <= i <= 100) 가 주어집니다.

입력으로 주어진 얼음을 규칙대로 깼을 때 얻을 수 있는 가장 높은 점수를 출력해 주세요.