Podium

Cerință

La un turneu de șah au participat $n$ animale. Pentru fiecare animal se cunoaște dacă este terestru sau acvatic, cât și înălțimea lui $h_i$. Animalele sunt numerotate de la $1$ la $n$ în ordinea scorului obținut.

La festivitatea de premiere, se dorește ca acestea să fie dispuse în ordine strict crescătoare, pentru ca poza să reflecte clasamentul. La început, înălțimile lor $h_1,h_2,\dots,h_n$ nu sunt neapărat ordonate, dar cum animalele acvatice stau într-un acvariu, acesta poate fi ridicat de la pământ cu un număr întreg de unități.

În alte cuvinte, dacă $i_1,i_2,\dots,i_k$ sunt animalele acvatice, atunci $h_{i_1},h_{i_2},\dots,h_{i_k}$ pot fi crescute cu același număr întreg de unități $x$ ($0\le x\le 10^9$), iar la final se dorește ca $h_1<h_2<\dots<h_n$. Determinați dacă există soluție, iar în cazul în care există, afișați o posibilă valoare $x$.

Date de intrare

Pe prima linie se va afla un număr $n$ (numărul de animale). Pe a doua linie se vor afla $n$ numere $h_1,h_2,\dots,h_n$ (înălțimile animalelor). Pe a treia linie se vor afla $n$ numere $a_1,a_2,\dots,a_n$ din mulțimea $\{0,1\}$. $a_i=1$ dacă și numai dacă animalul $i$ este acvatic.

Date de ieșire

Pe prima linie se va afișa un singur număr întreg $x$, reprezentând numărul de unități cu care ar putea fi ridicat acvariul astfel încât condiția să fie respectata. Trebuie să se respecte $0\le x\le 10^9$. Dacă nu există soluție, se va afișa $-1$.

Restricții și precizări

Pentru toate testele, se respectă $2 \le n \le 10^5$ și $1\le h_i\le 10^9$.

Exemplul 1

stdin

4
2 1 6 4
0 1 0 1

stdout

3

Explicație

Exemplul este ilustrat în imaginea de mai sus. Înălțimile animalelor după ridicarea acvariului vor fi 2 4 6 8. Singura altă soluție posibilă este $x=4$.

Exemplul 2

stdin

5
2 1 4 6 4
0 1 0 0 1

stdout

-1

Explicație

În acest caz, nu există soluție. De exemplu, pentru $x=3$, obținem înălțimile 2 4 4 6 7. Acestea nu sunt în ordine strict crescătoare.

Exemplul 3

stdin

3
7 7 7
0 1 1

stdout

-1

Exemplul 4

stdin

4
2 1 2 1
0 0 1 1

stdout

-1

Exemplul 5

stdin

4
1 2 3 4
1 1 1 1

stdout

1000000000

Explicație

În acest caz, orice soluție $0\le x\le 10^9$ este corectă.