매력적인 울타리

상근이는 높이가 모두 다른 N개의 나무 판자를 이용해 울타리를 만들려고 한다. 각 판자의 높이는 10^9보다 작은 양의 정수이다.

울타리의 매력도는 서로 인접한 두 판자의 높이 차이의 절댓값을 모두 더한 값이다.

상근이는 이미 판자 N개를 사 왔지만, 어떤 순서로 배치할지 아직 정하지 못했다. 그는 동규의 울타리와 비슷한 모양을 유지하면서 매력도를 최대한 크게 만들고 싶다.

두 울타리가 비슷하다는 것은 모든 i에 대해 인접한 두 판자의 높낮이 관계가 같다는 뜻이다. 즉, 동규의 i번째 판자가 i+1번째 판자보다 높다면 상근이의 i번째 판자도 i+1번째 판자보다 높아야 하고, 동규의 i번째 판자가 더 낮다면 상근이의 i번째 판자도 더 낮아야 한다.

동규의 울타리 높이와 상근이가 구매한 판자 높이가 주어질 때, 동규의 울타리와 비슷하면서 매력도가 가장 큰 상근이의 울타리를 구하라.

상근이가 구매한 판자의 높이는 모두 서로 다르고, 동규의 울타리를 이루는 판자의 높이도 모두 서로 다르다.

첫째 줄에 정수 N이 주어진다. (2 <= N <= 300,000)

둘째 줄에 동규의 울타리를 이루는 N개 판자의 높이가 순서대로 주어진다.

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

첫째 줄에 만들 수 있는 울타리의 최대 매력도를 출력한다.

둘째 줄에 그 최대 매력도를 만드는 상근이의 울타리 높이를 순서대로 공백으로 구분해 출력한다.

최적의 울타리가 여러 가지라면 그중 아무 것이나 출력해도 된다.