문제
메이플 월드의 잠꾸러기 웡키는 N 마리의 주황버섯과 함께 일자 맵에서 살고 있다.
일자 맵의 위치는 양의 정수 x 에 대해 웡키를 기준으로 왼쪽으로 x 만큼 떨어져 있으면 위치 -x 에 있다고 표현하고,
오른쪽으로 x 만큼 떨어져 있으면 위치 x 에 있다고 표현하고, 윙키가 위치한 곳에 있으면 위치 0에 있다고 표현한다.
각 주황버섯은 매 분마다 왼쪽으로 1 만큼, 오른쪽으로 1 만큼 혹은 제자리로 점프한다.
즉, 현재 주황버섯이 위치 p 에 있으면 1 분 뒤에는 위치 p-1 에 있거나, 위치 p에 있거나 위치 p+1에 있다.
요정 웡키는 주황버섯들이 점프하자마자 모든 주황버섯의 위치를 기록하고 잠들었다.
기록하고 잠드는 데에는 시간이 걸리지 않는다 가정하자.
같은 위치에 두 마리 이상의 주황버섯이 존재할 수도 있다.
1 분 이상 잠을 잔 후 잠에서 깨어난 웡키는 즉시 모든 주황버섯의 위치를 기록했다.
이때 깨어나서 기록하는 데에는 시간이 걸리지 않는다고 가정하고,
주황버섯은 모두 똑같이 생겨서 서로 구분할 수 없다.
문득 웡키는 두 기록을 가지고 자신이 최소 몇 분 잤는지 궁금해졌다.
요정 웡키를 도와 웡키가 최소 몇 분 잤는지 구해주자.
입력
첫 줄에 주황버섯의 수 N이 주어진다. (1≤N≤100 000)
두 번째 줄에 웡키가 잠에 들기 전에 적어둔 주황버섯의 위치 N 개가 공백으로 구분되어 주어진다.
세 번째 줄에 웡키가 잠에서 깨어난 후에 주황버섯의 위치 N 개가 공백으로 구분되어 주어진다.
주어지는 모든 위치는 -1,000,000,000 이상 1,000,000,000 이하이다.
종류 1 (11점): N≤10
출력
첫 줄에 웡키가 잔 최소 시간을 출력한다.
예제 #1
5
1 3 4 6 10
8 3 5 –2 16
6
예제 #2
5
1 1 1 1 1
5 5 5 5 5
4
예제 #3
1
1
1
1