시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 14 7 7 58.333%

문제

상근이네 마을의 울타리는 모두 높이가 다른 N개의 판자로 만든다. 상근이는 아직 울타리를 가지고 있지 않았기 때문에, 이번 기회에 만들기로 했다.

나무 판자는 109보다 작은 양의 정수로 나타낼 수 있다. 이 정수는 판자의 높이를 나타낸다.

울타리의 매력도는 인접한 판자의 높이 차이의 합이다.

상근이는 이미 나무 판자를 상점에서 사왔다. 하지만, 어떠한 순서로 울타리를 만들어야 하는지 결정하지 못했다. 결국 상근이는 동규의 울타리와 비슷하게 울타리를 만드려고 한다. 그러면서 매력도를 가능한 크게 만드려고 한다.

인접한 두 나무 판자의 높이의 대소관계가 일치한다면, 두 울타리가 비슷하다고 한다. 즉, 두 울타리 모두 i번 판자가 (i+1)번 판자보다 커야(작아야) 한다.

동규의 울타리의 높이와 상근이가 구매한 나무 판자의 높이가 주어졌을 때, 동규의 울타리와 비슷하면서 매력도가 가장 큰 울타리를 만드는 프로그램을 작성하시오.

상근이의 울타리의 높이가 모두 각각 다르고, 동규의 울타리의 높이가 모두 각각 다르다.

입력

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 300,000)

둘째 줄에 동규의 울타리를 구성하는 판자의 높이가 주어진다.

셋째 줄에 상근이가 구매한 판자의 높이가 주어진다.

출력

첫째 줄에 상근이의 울타리의 매력도를 출력한다.

둘째 줄에 상근이의 울타리를 구성하는 나무 판자의 높이를 공백으로 구분해 출력한다.

예제 입력

4
5 7 4 9
1 2 3 4

예제 출력

7
2 4 1 3

힌트

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #4 4번

  • 문제를 번역한 사람: baekjoon
  • 빠진 조건을 찾은 사람: koosaga