N개의 정수가 일렬로 주어진다. 이 수열을 순서를 바꾸지 않고 연속된 4개의 그룹으로 분할해야 한다. 각 그룹은 적어도 1개 이상의 수를 포함해야 한다.

각 그룹의 점수는 그룹 내에 속한 모든 수의 합이다. 4개 그룹의 점수를 모두 곱한 '최종 시너지 점수'의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수 N이 주어진다.

둘째 줄에 N개의 정수가 공백으로 구분되어 순서대로 주어진다.

출력

연속된 4개의 그룹으로 분할하여 얻을 수 있는 최종 시너지 점수의 최댓값을 첫째 줄에 출력한다.

제한 사항

• 4 ≤ N ≤ 100
• 각 정수는 -10 이상 10 이하이다.

예제 입력 1

6
2 -2 -4 2 -2 -2

예제 출력 1

96

예제 설명 1

재료를 [2], [-2, -4], [2], [-2, -2]의 4개 그룹으로 분할하면 다음과 같이 계산된다.

• 1그룹 합: 2
• 2그룹 합: (-2) + (-4) = -6
• 3그룹 합: 2
• 4그룹 합: (-2) + (-2) = -4 최종 점수는 2 (-6) 2 * (-4) = 96이 된다.