Frizura
시간 제한1초메모리 제한1024 MB
현재 머리카락 길이와 목표 길이가 주어질 때, 연속한 구간을 한 높이에서 자르는 연산의 최소 횟수로 목표에 도달하는 방법을 구하고, 불가능하면 -1을 출력합니다.
문제
Mali Matej član je povjerenstva za provedbu i evaluaciju brojnih hrvatskih informatičkih natjecanja. Budući da je taj posao izuzetno stresan, Matej se s vremena na vrijeme hvata za glavu te, uslijed erupcije emocija, iščupa poneki pramen kose. Srećom, Matej je odlučio stati na kraj lošoj frizuri pa je pomno izmjerio duljine preostalih vlasi i skicirao željenu frizuru. Preostalo mu je samo osmisliti optimalan algoritam za pretvorbu svoje trenutne frizure u željenu frizuru, a za to mu je potrebna vaša pomoć.
Mateju je na glavi preostao niz od N vlasi kose. Za svaku vlas kose poznata mu je njena trenutna i željena duljina. Matej je kosu odlučio rezati škarama te u jednom potezu može uzeti neki uzastopni podniz vlasi te škarama napraviti rez na proizvoljnoj visini h. Odredite najmanji broj rezova kojim Matej može svoju trenutnu frizuru pretvoriti u željenu frizuru.
입력
U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 200 000) koji označava broj vlasi na Matejevoj glavi.
U drugom retku nalazi se N prirodnih brojeva Ai (1 ≤ Ai ≤ 109) odvojenih razmakom koji predstavljaju trenutne duljine Matejevih vlasi u nanometrima.
U trećem retku nalazi se N prirodnih brojeva Bi (1 ≤ Bi ≤ 109) odvojenih razmakom koji predstavljaju željene duljine Matejevih vlasi u nanometrima.
출력
U jedini redak ispišite najmanji broj rezova potreban da Matej pretvori trenutnu frizuru u željenu frizuru. U slučaju da to nije moguće, ispišite -1.