펜스

프로그램 명: coci_ograda(special judge)

제한시간: 1 초

미코의 마을에는 모든 울타리는 다른 높이의 N 개의 보드로 만들어져 있다. 미코는 자신의 집의 울타리가 아직 없어 건설하기로 결정 했다.

모든 보드는 양의 정수로 높이를 나타낸다. 크기는 10^9 보다 작다. 멋진 펜스(niceness)의 기준을 인접한 보드 사이의 높이의 차의 합으로 정의한다.

미코는 보드를 미리 사놓아 어떤 보드를 주문해야 할지는 생각할 필요가 없다. 그는 슬라브코의 펜스와 비슷하게 펜스를 만들기를 원하지만 또한 가능한 멋지게도 하고 싶다.

인접한 보드의 나열의 높 낮이가 같다면 즉 i 번째 보드가 i+1 번째 보드 보다 크면 크고 , 작으면 작은 상태로 배열되면 두 펜스는 비슷하다고 한다. (다음 문장 번역 매끄럽게 해 주실 분: We say that two fences are similar if ordering of adjacent boards is the same in both fences, i.e. if i-th board of one fence is smaller (or larger) than (i+1)-st, than the same must hold for that boards of the other fence.)

슬라브코의 펜스 상태와 미코가 산 보드의 높이가 주어질 때 , 미코의 펜스를 슬라브코와 비슷하지만 가능한 멋지게 놓아라. 여러개의 답이 존재한다면 그 중 하나를 출력한다.

In Mirko’s village all fences are made of exactly 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 - it’s 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 ordering of adjacent boards is the same in both fences, i.e. if i-th board of one fence is smaller (or larger) than (i+1)-st, than the same must hold for that boards of the other fence.

Given Slavko’s fence configuration, and 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.

입력

The first line of input contains integer N (2 ≤ N ≤ 300 000), number of boards in each fence. The following line conatins N different positive integers representing Slavko’s fence. The following line contains N different positive integers representing heights of boards Mirko bought for his fence.

출력

The first line of output should contain the maximum possible niceness of Mirko’s fence. The following line should contain N integers, Mirko’s boards in optimal order as described.

입출력 예

input

4
5 7 4 9
1 2 3 4

output

7
2 4 1 3

input

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

output

3010
100 80 10 40 50 1000 20 70 500 30

SAMPLE TESTS

First sample description: Mirko bought boards of heights 1, 2, 3 and 4. Fences similar to Slavko’s that he can build are:

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

출처:coci 2012 contest5 4/6

[질/답] [제출 현황] [푼 후(0)]

[ 채 점 ] [홈으로] [뒤 로]