수 묶기

길이가 N인 정수 수열이 주어진다. 수열의 합을 크게 만들기 위해 서로 다른 두 수를 선택해 하나의 묶음으로 만들 수 있다. 묶인 두 수는 합에 각각 더하지 않고, 두 수의 곱을 더한다.

각 수는 최대 한 번만 묶을 수 있으며, 묶지 않은 수는 그대로 합에 더한다. 두 수는 수열에서의 위치와 상관없이 묶을 수 있지만, 같은 원소를 자기 자신과 묶을 수는 없다.

예를 들어 수열이 {0, 1, 2, 4, 3, 5}이면 그대로 더한 합은 15이다. 하지만 2와 3, 4와 5를 각각 묶으면 0 + 1 + (2 * 3) + (4 * 5) = 27이 되어 더 커진다.

수열이 주어졌을 때, 수를 적절히 묶거나 묶지 않아서 만들 수 있는 합의 최댓값을 구하시오.

첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다.

둘째 줄부터 N개의 줄에 수열의 각 수가 하나씩 주어진다. 각 수는 -1000 이상 1000 이하인 정수이다.

수를 적절히 묶어서 만들 수 있는 합의 최댓값을 출력한다. 정답은 항상 2^31보다 작다.