준영이의 사랑

선린의 대표 스윗남인 준영이는 여자친구 아스나를 위한 선물을 준비 중이다. 그는 $N$개의 진주로 이루어진 원형 진주 목걸이를 선물할 생각이다.

$i$ $(1 \leq i \leq N)$번째 진주알의 가치는 $P_{i}$이다. 준영이는 이 진주알 $N$개를 적당한 순서로 재배열하여 목걸이의 가치가 최대가 되도록 하려고 한다. 재배열한 후 $i$번째 진주알의 가치를 $A_i$ $(1 \leq i \leq N)$라 하자. 목걸이의 가치 $X$는 서로 인접한 진주알 쌍마다 두 진주알의 가치를 곱한 값을 모두 더한 것이다.

$X=A_{1}\times A_{2}+A_{2}\times A_{3}+\cdots+A_{N-1}\times A_{N}+A_{N}\times A_{1}$

목걸이 가치 $X$의 최댓값과, 그 가치가 나오도록 재배열했을 때의 $i$번째 진주알 가치 $A_i$를 출력하라. 가치가 최대인 배치가 여러 개면 그중 하나를 출력하면 된다.

첫째 줄에 진주알의 개수 $N$이 주어진다.

둘째 줄에 각 진주알의 가치 $P_1, P_2, \cdots, P_N$이 공백으로 구분되어 주어진다.

입력되는 수는 모두 정수이다.

첫째 줄에 목걸이 가치의 최댓값 $X$를 출력하라.

둘째 줄에 그 가치가 나오도록 재배열한 목걸이의 각 진주알 가치 $A_1, A_2, \cdots, A_N$을 공백으로 구분하여 출력하라.

• $3 \leq N \leq 2\,000$
• $1 \leq P_{i} \leq 1\,000$ $(1 \leq i \leq N)$