수열의 점수

정수 n개로 이루어진 수열이 주어진다. 한 번의 작업에서는 수열에서 정수 하나를 골라 제거하거나, 서로 다른 두 정수를 골라 함께 제거할 수 있다.

정수 하나를 제거하면 그 정수의 값이 점수에 더해지고, 두 정수를 제거하면 두 정수의 곱이 점수에 더해진다. 모든 정수를 제거할 때까지 작업을 반복할 때 얻을 수 있는 총점의 최댓값을 구하라.

예를 들어 수열이 -1, 5, -3, 5, 1이라면, 1을 혼자 제거하고, 5와 5를 함께 제거하고, -1과 -3을 함께 제거할 수 있다. 이때 얻는 점수는 각각 1, 25, 3이므로 총점은 29가 된다.

첫째 줄에 정수 n이 주어진다. (1 ≤ n ≤ 100,000)

다음 n개의 줄에는 수열을 이루는 정수가 한 줄에 하나씩 주어진다. 각 정수의 절댓값은 1,000,000을 넘지 않는다.

얻을 수 있는 총점의 최댓값을 출력한다.