G. Qutilar
220 ball
Omborda N ta to‘g‘ri to‘rtburchak shaklidagi quti bor. i-qutining eni aᵢ, bo‘yi bᵢ.
j-qutini k-qutining ichiga solish mumkin, agar aⱼ < aₖ va bⱼ < bₖ bo‘lsa — ya’ni eni ham, bo‘yi ham qat’iy kichik bo‘lsa. Qutilarni burab (enini bo‘yi bilan almashtirib) bo‘lmaydi.
Bir nechta qutini matryoshka kabi ketma-ket bir-birining ichiga solish mumkin: birinchisi ikkinchisining ichiga, ikkinchisi uchinchisining ichiga va hokazo.
Bir-birining ichiga solinadigan qutilar zanjirining eng katta uzunligini toping.
Kirish ma’lumotlari
Birinchi qatorda bitta butun son N — qutilar soni.
Keyingi N ta qatorning har birida ikkita butun son: aᵢ va bᵢ.
Chiqish ma’lumotlari
Bitta butun son — eng uzun zanjirdagi qutilar soni.
Cheklovlar
1 ≤ N ≤ 10^5
1 ≤ aᵢ, bᵢ ≤ 10^9
Misollar
4 2 3 6 7 5 4 6 4
3
3 1 1 1 1 1 1
1
Tushuntirish
1-misol rasmda ko‘rsatilgan: 2×3 → 5×4 → 6×7. 6×4 qutini zanjirga qo‘shib bo‘lmaydi: 5×4 uning ichiga sig‘maydi (bo‘ylari teng), 6×4 esa 6×7 ning ichiga sig‘maydi (enlari teng).
2-misolda uchta bir xil quti bor — hech biri boshqasining ichiga sig‘maydi, javob 1.
Testlarning bir qismida N ≤ 8, bir qismida N ≤ 100 va N ≤ 5000. Masala qisman ball bilan baholansa, sekinroq yechim ham shu testlardan ball oladi.