로봇

시간 제한2초메모리 제한1024 MB

요약

직선 위에 있는 N개의 로봇과 N개의 안테나를 하나씩 활성화할 때, 매번 가장 가까운 로봇이 이동해 폭발한다. 로봇이 움직인 총거리를 최소로 하는 활성화 순서를 구한다.

문제

한 직선 위에 $1$ 번부터 $N$ 번까지 번호가 붙은 $N$ 개의 로봇과 $1$ 번부터 $N$ 번까지 번호가 붙은 $N$ 개의 안테나가 있다. 로봇 $i$ 의 좌표는 $a_i$ 이고 안테나 $i$ 의 좌표는 $b_i$ 이다. 모든 좌표는 서로 다르다.

현재 모든 안테나는 비활성 상태이다. 안테나를 하나씩 활성화하려고 한다. 안테나를 활성화하면 가장 가까운 로봇이 그 안테나로 이동하여 안테나와 함께 폭발한다. 가장 가까운 로봇이 둘이면 왼쪽 로봇만 이동한다.

로봇이 이동하는 거리의 합이 최소가 되도록 안테나를 활성화하는 순서를 구하라.

입력은 표준 입력에서 다음과 같은 형식으로 주어진다.

$N$

$a_1$ $a_2$ $\dots$ $a_N$

$b_1$ $b_2$ $\dots$ $b_N$

답을 다음과 같은 형식으로 출력한다.

$X$

$p_1$ $p_2$ $\dots$ $p_N$

여기서 $X$ 는 최소 이동 거리의 합이고, $p_i$ 는 $i$ 번째로 활성화하는 안테나의 번호이다.

답이 여러 개면 아무 것이나 출력해도 된다.