Կամուրջների կառուցում
Քաղաքի միջով հենց կենտրոնում հոսում է գեղեցիկ մի գետ։ Քաղաքային իշխանությունները ցանկանում են օգտակար կամուրջներ կառուցել, որպեսզի մարդիկ այլևս նավակներով չանցնեն գետը, ինչը այնքան էլ հարմար չէ։
Հայտնի է դարձել, որ կա
n կոորդինատների զույգ, որոնց միջև հնարավոր է կամուրջ կառուցել։ Միևնույն ժամանակ կա պահանջ, որ կամուրջները չխաչվեն (մեկ կամուրջը չի կարող անցնել մյուսի վրայով), թեև կարելի է օգտագործել նույն սկզբնական կամ վերջնական կետերը։Ելնելով այդ
n զույգերից՝ անհրաժեշտ է պարզել, թե առավելագույնը քանի կամուրջ կարելի է կառուցել՝ չխախտելով սահմանված պայմանները։
🌊
Կոորդինատները:
Կարող եք պատկերացնել գետը որպես կոորդինատային համակարգի OX առանցք։ Քաղաքի երկու մասերը գտնվում են X-առանցքից վերև և ներքև։ Ուստի, տրված կոորդինատները ցույց են տալիս կամրջի սկզբնակետի/վերջնակետի
x կոորդինատը:Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ 100 000)։Հաջորդ
n տողերում նշված են ամբողջ թվերից բաղկացած զույգեր , որոնք ներկայացնում են հնարավոր կամուրջների կոորդինատները (1 ≤ ≤ )։Ելք
Ծրագիրը պետք է տպի մեկ ամբողջ թիվ, որը ցույց է տալիս առավելագույն քանակի կամուրջները, որ հնարավոր է կառուցել։
Օրինակներ
Մուտք | Ելք |
4
2 6
5 4
8 1
10 2 | 2 |
6
1 3
2 4
3 5
4 6
5 1
6 2 | 4 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB