题目描述

设有个n活动的集合E={1,2,..,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间$s_i$和一个结束时间$f_i$,且$s_i < f_i$。如果选择了活动i,则它在时间区间 $[ s_i , f_i )$内占用资源。若区间$[ s_i , f_i )$与区间$[ s_j , f_j )$不相交，则称活动i与活动j是相容的。也就是说，当$f_i \leq s_j$或 $f_j \leq s_i$时，活动i与活动j相容。选择出由互相兼容的活动组成的最大集合。

输入描述

第一行一个整数n 接下来的n行，每行两个整数$s_i$和$f_i$。

输出描述

输出互相兼容的最大活动个数。

示例1

输入

4
1 3
4 6
2 5
1 7

输出

2

输入样例 #2

65
550 607
948 1509
711 1054
228 446
277 439
447 1056
823 833
325 528
597 1548
137 618
127 484
964 1573
503 1199
841 1068
213 1080
271 672
760 1699
33 203
813 1161
520 1164
674 823
289 965
81 801
977 1112
57 214
531 1429
230 507
58 635
621 1455
65 91
122 683
14 546
961 1802
367 1094
395 512
596 648
145 507
269 526
113 453
604 1440
390 1039
130 872
649 1077
50 189
754 1113
333 758
666 1269
151 250
640 931
506 516
958 1449
361 918
737 1370
957 1623
937 1855
651 1320
344 366
210 886
453 598
795 1501
847 1007
873 1343
861 1677
251 679
328 1020

输出样例 #2

8

输入样例 #3

207
45 81
968 1955
438 515
766 1740
579 933
102 240
79 279
814 1413
566 1032
430 796
368 1024
595 1202
974 1951
152 335
407 653
757 1286
355 1240
102 451
590 1147
122 775
801 1078
430 1249
334 565
160 1071
545 1153
159 626
244 1028
28 480
679 1348
887 1120
637 919
3 533
935 1295
9 47
56 293
63 376
346 630
729 1467
946 1805
845 1447
951 1198
351 673
758 1354
651 1098
194 805
903 1062
411 1194
211 1022
853 1191
962 1511
315 745
768 1520
819 1647
894 1505
221 977
764 1047
524 1332
823 900
4 145
431 724
140 604
248 980
727 1268
335 1277
447 877
597 1323
762 1661
6 500
878 1613
391 417
170 948
9 391
65 68
123 483
927 1217
208 603
894 1202
328 687
998 1441
467 948
14 300
41 635
621 860
714 919
61 204
107 276
880 1273
798 1611
28 440
121 787
254 369
35 220
811 1088
615 622
724 1690
669 1189
865 1614
833 1376
543 1123
290 1044
969 1665
848 1702
19 515
600 1589
126 521
287 323
938 1206
228 1182
970 1108
650 1481
848 1321
174 780
428 966
224 878
518 884
239 440
230 1048
932 1072
455 1342
458 608
171 677
980 1651
393 1281
599 1212
266 632
252 1010
466 1142
927 1076
701 1568
816 1340
752 1183
474 668
747 1517
961 1378
489 1090
741 1571
920 1465
670 1593
924 940
38 139
438 1279
740 1480
32 810
846 990
993 1377
550 1268
891 1751
178 1087
828 1516
899 1368
16 754
795 1045
941 1227
546 1132
707 744
94 299
294 325
879 1445
655 938
390 491
625 1509
33 920
523 536
548 1333
711 1015
650 1465
995 1123
436 628
145 528
162 343
934 1119
848 1048
889 1270
76 272
505 1445
541 751
511 834
633 1292
930 1833
303 730
455 755
431 997
354 1170
480 521
658 1476
426 760
329 1123
410 797
613 1354
374 1004
130 425
195 876
638 975
44 770
859 1757
139 775
608 783
928 1195
280 828
45 998
703 957
571 1058
457 781
272 750
60 153
20 873
391 530

输出样例 #3

12

数据范围

$1 \leq n \leq 1000$