댐

바이토시아에 거대한 저수지를 만들었다. 저수지는 길이가 모두 같은 여러 개의 구획으로 나뉘어 있다. 이웃한 두 구획 사이마다 일정한 높이의 댐이 하나씩 세워져 있고, 첫 번째 구획 앞과 마지막 구획 뒤에도 댐이 세워져 있다.

지금은 저수지 전체의 수위가 똑같다. 그런데 폭우가 내리기 시작해 수위가 빠르게 오르고 있다. 왕은 물이 첫 번째 댐이나 마지막 댐을 넘쳐흐르기까지 시간이 얼마나 걸리는지 알고 싶어 한다. 물이 넘치면 나라 전체가 잠기고 만다. 구획마다 비가 내리는 세기가 다를 수 있어 계산이 까다롭다.

물이 저수지 밖으로 흘러넘치기까지 남은 시간을 구하여라. 수위가 댐 높이와 정확히 같을 때는 아직 넘치지 않은 것으로 본다. 물이 찬 구간이 양쪽에서 높이가 같은 두 댐으로 막혀 있으면, 물은 양쪽으로 똑같이 빠르게 넘쳐흐른다.

첫째 줄에 저수지가 나뉜 구획의 수를 나타내는 정수 $n$ ($1 \le n \le 500\,000$)이 주어진다.

둘째 줄에 공백 하나로 구분된 $n+1$개의 정수 $w_i$ ($1 \le w_i \le 1\,000\,000$)가 주어진다. 이는 처음 수위를 기준으로 한 각 댐의 높이를 왼쪽에서 오른쪽 순서로 나타낸다.

셋째 줄에 공백 하나로 구분된 $n$개의 정수 $k_i$ ($1 \le k_i \le 1\,000\,000$)가 주어진다. $k_i$는 $i$번째 구획에서 물이 1초 동안 몇 단계 높아지는지를 나타낸다.

물이 저수지 밖으로 흘러넘칠 때까지 걸리는 초의 수보다 작지 않은 가장 작은 정수 하나를 출력한다.