Untitled

import java.io.*;
import java.util.*;

public class Solution {
    public static int N, res;
    public static int[] arr, visited;
    
    public static int countScore(int x) {
        int leftScore = 0;
        int rightScore = 0;
        for (int i = x - 1; i >= 0; i--) {
            if (visited[i] == 0) {
                leftScore = arr[i];
                break;
            }
        }
        
        for (int i = x + 1; i < N; i++) {
            if (visited[i] == 0) {
                rightScore = arr[i];
                break;
            }
        }
        
        if (leftScore != 0 && rightScore != 0) {
            return leftScore*rightScore;
        }
        else if (leftScore == 0 && rightScore != 0) {
            return rightScore;
        }
        else if (leftScore != 0 && rightScore != 0) {
            return leftScore;
        }
        else {
            return arr[x];
        }
    }
    
    public static void backtrack(int step, int score) {
        
        if(step == N - 3) {
            int[] maintainBalls = new int[3];
            int numOfMaintainBalls = 0;
            for (int i = 0; i < N; i++) {
                if (visited[i] == 0) {
                    maintainBalls[numOfMaintainBalls] = arr[i];
                    numOfMaintainBalls++;
                }
            }
            
            int score1 = maintainBalls[1] + Math.max(maintainBalls[1], maintainBalls[2])*2;
            int score2 = maintainBalls[0]*maintainBalls[2] + Math.max(maintainBalls[0], maintainBalls[2])*2;
            int score3 = maintainBalls[1] + Math.max(maintainBalls[1], maintainBalls[0])*2;
            
            score += Math.max(score1, Math.max(score2, score3));
            if (res < score) {
                res = score;
            }
            score -= Math.max(score1, Math.max(score2, score3));
            
            return;
        }
        
        for (int i = 0; i < N; i++) {
            if (visited[i] == 0) {
                visited[i] = 1;
                backtrack(step+1, score+countScore(i));
                visited[i] = 0;
            }
        }
    }


    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        arr = new int[N];
        visited = new int[N];
        res = 0;
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        
        if (N == 1) {
            res = arr[0];
        }
        else if (N == 2) {
            res = Math.max(arr[0], arr[1]) * 2;
        }
        else {
            backtrack(0, 0);
        }
        System.out.println(res);
        sc.close();
    }
}