cho.shAttractive Fence
Time limit1sMemory limit128 MBProblem
Sanggeun wants to build a fence from N wooden planks, all with different heights. Each plank height is a positive integer less than 10^9.
The attractiveness of a fence is the sum of the absolute differences between the heights of every pair of adjacent planks.
Sanggeun has already bought the N planks, but he has not decided their order. He wants his fence to have the same up-and-down shape as Donggyu's fence while making the attractiveness as large as possible.
Two fences are considered similar if every adjacent pair has the same comparison direction. For every i, if Donggyu's i-th plank is higher than his i+1-st plank, then Sanggeun's i-th plank must also be higher than his i+1-st plank. If Donggyu's i-th plank is lower, then Sanggeun's i-th plank must also be lower.
Given the heights of Donggyu's fence and the heights of Sanggeun's purchased planks, construct a fence similar to Donggyu's with maximum attractiveness.
The purchased plank heights are all distinct, and the heights in Donggyu's fence are also all distinct.
Input
The first line contains an integer N. (2 <= N <= 300,000)
The second line contains the heights of the N planks in Donggyu's fence, in order.
The third line contains the heights of the N planks Sanggeun bought.
Output
On the first line, print the maximum possible attractiveness.
On the second line, print the heights of Sanggeun's fence in order, separated by spaces.
If there are multiple optimal fences, print any one of them.