수열 섞기
시간 제한1초메모리 제한512 MB
N개의 정수를 재배열해 인접한 원소끼리의 곱의 합이 최대가 되도록 만들고, 그 배치 하나를 출력한다.
문제
준원이는 이 문제를 각색하려고 했는데 너무 귀찮다. 그냥 풀어보도록 하자.
당신은 길이 N인 정수열 a1, …, aN을 가지고 있다. 이 수열을 재배열하여 인접한 원소의 곱들의 합, 즉 a1a2 + a2a3 + … + aN-1aN을 최대화하려고 한다. 이렇게 재배열한 수열을 하나 출력해 보자.
입력
첫째 줄에는 수열의 길이 N이 주어진다. (2 ≤ N ≤ 500,000)
둘째 줄에는 수열의 각 원소가 공백을 사이에 두고 주어진다. 각 원소의 절댓값은 100만 이하이다.
출력
인접한 원소의 곱들의 합을 최대화한 재배열을 하나 출력한다. 합을 최대화하는 재배열이 여러 가지라면 아무거나 하나 출력해도 된다.