Un trunchi de con este un corp geometric obtinut prin sectionarea unui con obisnuit, cu un plan paralel cu baza si inlaturarea conului mic rezultat.
Se da un sir de trunchiuri de con, definite prin razele celor doua baze. Inaltimile nu au importanta.
Găsiti cel mai lung subsir format din suprapunerea unor trunchiuri de con, alese in ordinea din sirul dat, astfel incat oricare doua corpuri consecutive sa fie lipite perfect (bazele lipite sa fie de aceeasi raza). Un corp poate fi rotit pentru a se potrivi perfect peste baza de deasupra a corpului anterior.

Cerinţă

Scrieti un proram care sa determine lungimea maxima a subsirului construit din trunchiurile de con astfel incat conditia de lipire perfecta sa fie satisfacuta. Ordinea corpurilor din subsir trebuie sa fie aceeasi din sirul initial.

Date de intrare

Fisierul de intrare conuri.in contine pe prima linie un numar N reprezentand numarul de trunchiuri de con din sirul initial.
Urmatoarele N linii contin perechi de numere R1 R2, separate prin spatiu, reprezentand razele bazelor celor N trunchiuri de con.

Date de ieşire

Fisierul de iesire conuri.out va contine un singur numar reprezentand lungimea maxima a subsirului ce poate fi construit.

Restricţii

• 1 <= N <= 100000
• 1 <= R1, R2 <= 100000

Exemple

conuri.in	conuri.out
5 1 5 2 4 1 2 3 4 4 1	3

Alex Palcuie Robert Hasna Andrei Vacaroiu

Universitatea din Bucuresti