잠꾸러기

메이플 월드의 잠꾸러기 웡키는 $N$ 마리의 주황버섯과 함께 일자 맵에서 살고 있다.

일자 맵의 위치는 양의 정수 $x$ 에 대해 웡키를 기준으로 왼쪽으로 $x$ 만큼 떨어져 있으면 위치 $-x$ 에 있다고 표현하고, 오른쪽으로 $x$ 만큼 떨어져 있으면 위치 $x$ 에 있다고 표현하고, 윙키가 위치한 곳에 있으면 위치 $0$에 있다고 표현한다.

각 주황버섯은 매 분마다 왼쪽으로 $1$ 만큼, 오른쪽으로 $1$ 만큼 혹은 제자리로 점프한다. 즉, 현재 주황버섯이 위치 $p$ 에 있으면 $1$ 분 뒤에는 위치 $p-1$ 에 있거나, 위치 $p$에 있거나 위치 $p+1$에 있다.

요정 웡키는 주황버섯들이 점프하자마자 모든 주황버섯의 위치를 기록하고 잠들었다. 기록하고 잠드는 데에는 시간이 걸리지 않는다 가정하자. 같은 위치에 두 마리 이상의 주황버섯이 존재할 수도 있다.

$1$ 분 이상 잠을 잔 후 잠에서 깨어난 웡키는 즉시 모든 주황버섯의 위치를 기록했다. 이때 깨어나서 기록하는 데에는 시간이 걸리지 않는다고 가정하고, 주황버섯은 모두 똑같이 생겨서 서로 구분할 수 없다.

문득 웡키는 두 기록을 가지고 자신이 최소 몇 분 잤는지 궁금해졌다. 요정 웡키를 도와 웡키가 최소 몇 분 잤는지 구해주자.

입력 형식

첫 줄에 주황버섯의 수 $N$이 주어진다. ($1 \le N \le 100\,000$)

두 번째 줄에 웡키가 잠에 들기 전에 적어둔 주황버섯의 위치 $N$ 개가 공백으로 구분되어 주어진다.

세 번째 줄에 웡키가 잠에서 깨어난 후에 주황버섯의 위치 $N$ 개가 공백으로 구분되어 주어진다.

주어지는 모든 위치는 $-1\,000\,000\,000$ 이상 $1\,000\,000\,000$ 이하이다.

출력 형식

첫 줄에 웡키가 잔 최소 시간을 출력한다.

예제 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

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설