Անվերջ երկար միջանցքում փռված են N հատ խալիներ։ Միջանցքը բաժանված է հավասարաչափ մասերի, որոնք համարակալված են ամբողջ թվերով։ Ամեն մասի վրա դրված է մեկ հատ սալիկ։ i-րդ խալին ծածկում է l[i]-իցr[i] համարները ունեցող սալիկները (ներառյալ l[i] և r[i] համարները ունեցող սալիկները)։ Նկատենք, որ մի քանի խալի կարող են ծածկել միևնույն սալիկը։ Ձեր խնդիրն է գտնել խալիների մաքսիմալ քանակը, որոնք ծածկում են գոնե մեկ ընդհանուր սալիկ։
Մուտքային տվյալներ
Առաջին տողում տրված են խալիների N (1 ≤ N ≤ 100 000) քանակը։ Հաջորդ N տողերից յուրաքանչյուրում տրված են երկուական թվեր՝ հերթական խալու ծածկած սալիկների հատվածը նկարագրող l[i] և r[i] թվերը (1 ≤ l[i] ≤ r[i] ≤ 109)։
Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝ խալիների մաքսիմալ քանակը, որոնք ծածկում են գոնե մեկ ընդհանուր սալիկ։
Օրինակներ
Մուտք
Ելք
4
1 2
2 3
3 3
3 4
3
Գնահատում
Թեստերի 25 տոկոսում N ≤ 1000 և r[i] ≤ 1000: Թեստերի մեկ այլ 50 տոկոսում r[i] ≤ 1000 000: