16209번 - 수열 섞기 서브태스크스페셜 저지

준원이는 이 문제를 각색하려고 했는데 너무 귀찮다. 그냥 풀어보도록 하자.

당신은 길이 N인 정수열 a₁, …, a_N을 가지고 있다. 당신은 이 수열을 재배열하여, 수열에서 인접한 원소의 곱들의 합, 즉 a₁a₂ + a₂a₃ + … + a_N-1a_N을 최대화하려고 한다. 이렇게 재배열한 수열을 하나 출력해 보자.

첫째 줄에는 수열의 길이 N이 주어진다. (2 ≤ N ≤ 500,000)

둘째 줄에는 수열의 각 원소가 공백을 사이에 두고 주어진다. 각 원소의 절댓값은 100만 이하이다.

인접한 원소의 곱들을 최대화한 본 수열의 재배열을 하나 출력하자. 만약 최대화할 수 있는 재배열이 여러 가지 있다면 아무거나 하나 출력하면 된다.

N ≤ 5를 만족한다.

수열의 각 원소는 양의 정수 또는 0이다.

문제에 제시된 조건 이외의 다른 제약은 없다.