FMI NO STRESS 13 | Invitația la vals

This was the problem page during the contest. Access the current page here.
Time limit: 1s Memory limit: 256MB Input: Output:

Cerință

Ca în fiecare an, la Opera din Viena se organizează un bal. Anul acesta sunt invitați NN tineri băieți și NN tinere fete, și toți trebuie să danseze primul vals al serii pe un ring circular. Cei 2N2N invitați stau pe marginea ringului, unde stă și MC-ul (Maestrul de Ceremonii) al balului, cancelarul Austriei.

Cum valsul se dansează în perechi, băieții trebuie să-și aleagă partenere de dans. Ei și le aleg după următoarea regulă:

  • Începând cu cel mai apropiat de el în sens invers acelor de ceas și mergând în același sens, cancelarul va striga, pe rând, numele băieților.
  • Când unui băiat i se strigă numele, va merge înainte de-a lungul marginii ringului, în sens invers acelor de ceas, până întâlnește prima fată care nu a fost invitată la vals, și o invită.
  • Deoarece fetele nu sunt foarte pretențioase, ele nu refuză niciodată Invitația la vals.
  • După ce fata acceptă, perechea nou formată merge spre centrul ringului, după care este spus un nou nume și procesul se reia.

Cancelarul vrea să știe numărul de băieți care vor trece prin fața lui, în drumul spre a-și găsi partenera, și vă cere ajutorul.

Date de intrare

Pe prima linie este un număr natural NN, ca în enunț. Pe următoarea linie se află NN numere naturale FiF_i, descriind pozițiile celor NN fete. Pe a treia linie se află NN numere naturale BiB_i, descriind pozițiile celor NN băieți. Pozițiile sunt definite prin distanța pe care ar trebui s-o parcurgă cancelarul în sens invers acelor de ceas ca să ajungă la el/ea.

Date de ieșire

Se va afișa un singur număr natural, răspunsul la întrebarea cancelarului.

Restricții și precizări

  • 1N200 0001 \leq N \leq 200 \ 000;
  • 1Fi,Bi1081 \leq F_i, B_i \leq 10^8;
  • Cancelarul nu se mișcă pe durata formării perechilor;
  • Niciun invitat nu stă exact în dreptul cancelarului, și nu există doi invitați cu aceeași poziție.
  • Ringul de dans al Operei din Viena este imens, are lungime 108+110^8+1;
  • Pentru teste în valoare de 1515 puncte, N15N \le 15;
  • Pentru alte teste în valoare de 2525 de puncte, N1 000N \le 1\ 000;
  • Pentru alte teste în valoare de 6060 de puncte, nu există restricții suplimentare.

Exemplu

stdin

3
2 7 11 
3 12 1

stdout

1

Explicație

Aceasta este configurația inițială pe ringul de dans. Desenul nu este la scară, pentru simplitate.

Primul pleacă băiatul de la distanța 11, care va dansa cu fata de la distanța 22, deoarece ea e prima care îi iese în drum.

După el, va pleca băiatul de la distanța 33, care o va întâlni prima pe fata de la distanța 77 și va dansa cu ea.

Când pleacă băiatul de la distanța 1212, mai e disponibilă doar fata de la distanța 1111, deci pe ea o va invita la dans, fiind nevoit să treacă prin fața cancelarului (care stă la distanța 00 de sine însuși).

El e singurul care face asta, deci răspunsul final e 11.

Log in or sign up to be able to send submissions!