COCI '11 Contest 4 #4 Ograda

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 32M

Problem type

In Mirko's village, all fences are made of exactly $N$ $N$ boards with different heights. Mirko doesn't have his own fence yet, so he decided to build one.

Each board is represented by a positive integer less than $10^9$ $10^{9}$ - its height. We define the niceness of the fence as a sum of height differences between adjacent boards.

Mirko already bought the boards, but he doesn't know how to order them into a fence. He would like his fence to be similar to Slavko's fence, but also to be as nice as possible.

We say that two fences are similar if the ordering of adjacent boards is the same in both fences, i.e. if $i^\text{th}$ $i^{th}$ board of one fence is smaller (or larger) than $(i+1)^\text{st}$ $(i + 1)^{st}$ , then the same must hold for the boards of the other fence.

Given Slavko's fence configuration, and the heights of boards that Mirko bought, put Mirko's fence together so that it is similar to Slavko's but also as nice as possible. If there is more than one solution, output any of them.

Input Specification

The first line of input contains integer $N$ $N$ $(2 \le N \le 300\,000)$ $(2 \leq N \leq 300 000)$ , number of boards in each fence.

The following line contains $N$ $N$ different positive integers representing Slavko's fence.

The following line contains $N$ $N$ different positive integers representing heights of boards Mirko bought for his fence.

Output Specification

The first line of output should contain the maximum possible niceness of Mirko's fence.

The following line should contain $N$ $N$ integers, Mirko's boards in optimal order as described.

Scoring

$50\%$ $50 %$ of the points for a test case will be awarded if niceness is correct, but the second line is incorrect or not outputted at all.

Sample Input 1

Copy

4
5 7 4 9
1 2 3 4

Sample Output 1

Copy

7
2 4 1 3

Explanation for Sample Output 1

Mirko bought boards of heights $1$ $1$ , $2$ $2$ , $3$ $3$ and $4$ $4$ . Fences similar to Slavko's that he can build are:

$\{1,3,2,4\}$ ${1, 3, 2, 4}$ - niceness $2+1+2=5$ $2 + 1 + 2 = 5$ .
$\{1,4,2,3\}$ ${1, 4, 2, 3}$ - niceness $3+2+1=6$ $3 + 2 + 1 = 6$ .
$\{2,3,1,4\}$ ${2, 3, 1, 4}$ - niceness $1+2+3=6$ $1 + 2 + 3 = 6$ .
$\{2,4,1,3\}$ ${2, 4, 1, 3}$ - niceness $2+3+2=7$ $2 + 3 + 2 = 7$ .
$\{3,4,1,2\}$ ${3, 4, 1, 2}$ - niceness $1+3+1=5$ $1 + 3 + 1 = 5$ .

Sample Input 2

Copy

10
9 5 1 2 6 7 4 18 20 12
10 40 20 30 50 70 80 100 1000 500

Sample Output 2

Copy

3010
100 80 10 40 50 1000 20 70 500 30

Comments

There are no comments at the moment.