Խալիներ
Անվերջ երկար միջանցքում փռված են
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:Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB