【蓝桥杯】历届试题 连号区间数（运行超时）

  历届试题 连号区间数  

时间限制：1.0s   内存限制：256.0MB

      

问题描述

小明这些天一直在思考这样一个奇怪而有趣的问题：

在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：

如果区间[L, R] 里的所有元素（即此排列的第L个到第R个元素）递增排序后能得到一个长度为R-L+1的“连续”数列，则称这个区间连号区间。

当N很小的时候，小明可以很快地算出答案，但是当N变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

输入格式

第一行是一个正整数N (1 <= N <= 50000), 表示全排列的规模。

第二行是N个不同的数字Pi(1 <= Pi <= N)， 表示这N个数字的某一全排列。

输出格式

输出一个整数，表示不同连号区间的数目。

样例输入1

4
3 2 4 1

样例输出1

7

样例输入2

5
3 4 2 5 1

样例输出2

9

 

这道题运行超时了！以下是超时代码：

Java源代码：

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < a.length; i++) {
            a[i] = in.nextInt();
        }
        int count = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = i; j < a.length; j++) {
                if (isRight(a, i, j)) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }

    // 是否符合连号区间
    private static boolean isRight(int[] a, int i, int j) {
        if (i == j) {
            return true;
        }
        int[] b = new int[j - i + 1];
        for (int k = 0; k < b.length; k++) {
            b[k] = a[i + k];
        }
        Arrays.sort(b);
        for (int k = 0; k < b.length - 1; k++) {
            if (b[k] + 1 != b[k + 1])
                return false;
        }
        return true;
    }
}

评测点序号	评测结果	得分	CPU使用	内存使用	下载评测数据
1	正确	20.00	109ms	23.51MB	输入 输出
2	正确	20.00	234ms	24.41MB	输入 输出
3	正确	20.00	530ms	35.26MB	输入 输出
4	运行超时	0.00	运行超时	76.81MB	输入 输出
5	运行超时	0.00	运行超时	77.48MB	输入 输出

以下是4和5输入输出的数据，因为数据太大了所以超时了，以后有时间再去优化代码：

输入4为：

550
261 244 182 351 395 279 513 431 239 163 36 152 206 468 140 5 143 35 407 108 72 141 18 405 26 174 333 190 426 303 486 443 328 38 215 483 28 90 445 412 288 409 518 546 343 212 188 3 354 228 404 376 478 82 175 221 27 55 97 233 511 211 156 349 126 323 154 47 40 236 282 324 99 51 331 306 52 230 487 216 79 214 205 325 259 94 107 130 232 297 403 350 519 400 289 275 201 336 284 371 535 498 444 362 7 95 548 450 196 322 319 100 271 25 481 63 353 189 424 248 436 23 222 326 137 144 515 128 191 253 372 168 547 249 534 269 251 408 135 101 171 131 435 488 477 302 193 452 442 69 417 118 44 361 70 522 66 453 157 332 192 520 462 418 219 195 88 294 6 208 187 516 496 165 476 430 112 50 320 347 153 84 466 475 92 489 455 420 499 34 300 399 122 227 359 46 276 528 318 305 53 17 423 463 185 262 502 75 56 265 387 235 146 290 382 334 414 448 8 506 231 247 301 258 524 13 494 341 162 167 299 427 1 255 296 413 521 523 270 245 340 159 484 93 200 508 273 123 22 416 491 136 346 385 186 224 87 514 86 366 283 83 179 286 176 223 183 155 256 15 345 71 531 472 517 252 537 308 80 490 391 398 166 254 504 264 291 120 525 150 177 454 19 295 218 469 85 298 394 338 509 532 542 500 335 229 479 4 497 543 132 425 181 161 533 103 550 538 530 60 544 465 467 164 311 285 105 178 432 41 30 421 268 383 48 124 428 64 24 266 422 440 396 207 390 368 160 375 170 549 241 464 379 89 104 197 280 393 419 389 287 139 406 339 411 378 410 113 169 381 310 539 401 213 184 29 281 267 173 370 377 14 314 57 172 198 21 151 96 12 459 62 374 225 32 545 129 458 202 277 510 148 65 111 501 142 119 503 194 125 81 220 98 505 337 388 68 446 234 240 355 199 315 437 397 43 480 45 358 357 250 485 59 492 2 78 121 74 356 495 392 457 304 226 330 384 317 451 238 180 460 415 364 367 373 433 58 67 441 526 203 540 242 482 439 307 109 243 512 102 344 470 461 272 11 73 106 145 363 49 493 527 91 348 114 237 352 536 529 260 263 149 127 31 386 210 217 438 365 434 117 147 360 110 309 327 293 20 402 447 292 204 116 456 134 16 321 449 209 429 316 474 278 380 313 257 9 274 33 329 541 507 138 10 77 312 39 115 37 54 133 369 471 42 246 158 342 61 76 473

输出4为：

552

输入5为：

3984
913 3601 3029 3283 2142 1973 1617 378 91 3162 3642 1829 2319 1363 2265 1154 3423 3379 2115 226 2633 379 3394 550 2706 2885 608 3380 1744 2234 2354 408 3197 511 1098 2524 2020 41 1626 3025 366 2901 3929 74 1307 282 281 2229 1860 2214 1688 3372 3204 655 1037 618 3053 1180 2848 2888 1709 2710 1747 659 3289 3672 1799 3706 1927 447 3439 3063 1962 1082 2501 2984 356 1500 1941 64 138 1813 3012 587 1222 2391 3071 1978 1039 450 813 2075 733 713 3775 3435 3428 682 508 970 2621 589 3476 2149 1643 1821 1879 152 3038 3634 3575 1398 1317 502 2953 2822 475 2757 2375 1657 1054 3324 2859 3854 3300 3921 2294 3826 2514 3269 3817 1677 3615 3537 2813 2130 2380 1969 1654 2732 1570 342 1915 3225 3603 1100 1666 3354 2330 3546 1423 1703 2688 773 89 917 3360 196 1959 772 3833 3543 388 1189 3535 3485 403 2824 3798 2243 3248 525 3454 2310 962 3478 1719 3052 2648 2630 510 712 3873 3569 752 3362 3560 3572 3949 888 2029 993 3752 269 731 2305 98 1442 3237 2504 3098 193 3135 2737 3217 1970 2148 2 2006 3430 3403 387 868 1378 991 1944 3034 3542 1755 2898 1454 1281 3132 3827 1936 3220 1047 3761 2646 3965 380 1477 1547 1166 1052 3659 2455 3953 1046 3191 1945 1253 106 3373 2069 2871 253 988 847 1897 3845 284 3704 1951 777 2908 2193 2899 564 1652 3794 2049 310 3278 615 3429 3591 1955 267 2024 446 391 238 2263 2709 2172 3008 665 2749 2144 3057 3638 1212 1723 357 3875 3799 1450 1390 371 3508 1305 2445 1006 1531 1049 2702 3740 3737 2526 3010 198 325 192 2174 3240 1312 549 522 976 1728 432 2141 1456 3755 3046 2272 3357 3518 3449 3705 1568 2417 2770 562 2877 1346 1234 961 1594 1950 3151 2977 339 2548 2891 2606 2740 2661 1938 3099 3452 3421 2369 164 302 2790 2185 959 2165 2897 2077 2815 3075 3023 1099 3869 133 1279 2132 912 1977 1491 875 1022 2093 1329 3294 903 968 2346 2367 2066 81 594 2096 3940 667 760 1699 1169 496 2003 1712 3608 1205 1372 84 1139 574 108 1789 3306 1258 799 3229 1791 3222 1996 1268 2301 2857 2689 2920 3400 1823 3319 2065 946 3083 1932 1298 3330 2284 322 2041 1055 1844 864 1051 2302 1604 600 482 85 504 1002 190 1966 915 3017 678 3767 3137 2439 139 458 349 3588 2154 1920 3652 3959 3697 1185 2933 1539 2905 335 747 3858 691 3557 3943 2324 2207 817 2178 2199 1560 2316 1032 1382 2136 1865 2507 652 1830 1851 3779 2459 2643 2373 394 3930 788 2465 2186 3315 487 998 2632 1494 2189 1998 3426 3944 3365 369 869 3107 822 3169 2318 1908 1342 3166 1834 894 3004 3550 2043 166 2483 2612 3409 1459 2774 3519 3679 1289 2281 2705 1001 714 114 12 3964 457 473 1496 2202 658 2970 5 1586 790 2675 3133 851 3126 168 107 2562 352 3613 1380 1681 2332 1619 711 2476 346 3649 292 3743 718 1062 2637 3629 3690 2512 2769 3468 883 3196 3291 3179 1684 627 2275 3243 3718 1135 2973 2157 3707 3152 1625 399 1704 846 1503 2574 784 1598 3471 3181 690 1571 3818 1359 1178 1501 1489 842 2858 1722 3058 2254 1208 3051 29 1671 3130 867 2421 2826 1647 2536 1545 3548 1581 879 2986 1618 2934 2238 244 2693 130 340 2788 1176 3444 1136 3678 2649 622 2287 740 2832 1692 2609 2948 2353 1077 181 982 336 1861 351 1552 1990 79 1591 2699 1021 2915 1737 3839 3860 2181 1330 2050 542 3729 3865 3270 3651 3926 2094 1109 3856 1805 2598 126 3541 3529 2657 2292 288 1114 926 1934 1589 1968 2480 2729 592 3966 527 254 1112 1335 1211 2773 3251 3209 3253 2700 472 1864 885 914 3633 1825 393 56 1069 2126 593 3015 2209 3969 1634 180 931 3103 2466 2242 3797 641 1859 18 3195 2414 2554 1407 2694 375 47 1670 1318 2926 3864 645 3585 456 2360 1101 3206 3958 1649 2122 3974 3246 625 1928 2358 3030 2838 3482 617 494 580 222 693 154 3390 1123 503 2523 1311 3547 3298 53 2435 657 2055 3811 624 520 2978 2236 664 1320 1196 3632 178 1779 865 263 1170 2805 3887 1804 1036 2564 1517 3442 3532 909 3363 2880 2119 643 808 2204 2297 2565 3774 3555 1875 2731 3664 221 1786 1246 99 289 2893 1397 1070 577 2886 3673 3968 3238 268 1713 3787 3744 2549 2879 3933 985 2502 873 3089 3701 3474 17 2313 2325 400 3618 2726 1613 3722 2798 2746 2356 2078 1574 1308 3822 3682 1108 237 3739 303 3599 3407 1124 1511 452 1243 3041 3458 3947 113 22 1371 3593 1582 934 720 2910 1174 1632 3980 277 1470 1365 3813 3487 3937 3671 50 1764 103 485 1452 1527 721 229 2135 301 1714 2300 3090 3459 1796 797 2919 1765 372 3141 359 555 3840 240 850 258 1436 3623 383 2084 1600 3756 1204 2911 374 1876 330 1993 436 1528 521 2412 298 595 905 537 2428 1939 3657 3230 2654 1236 3801 1162 1758 2427 489 3325 1664 1102 1770 368 3340 2073 3391 996 316 2995 158 3486 3100 1071 3806 3016 3173 2394 1035 1832 2957 3279 3138 2608 2588 220 2596 2810 1651 2074 1992 2741 3345 2110 1753 1326 2928 942 102 3668 3726 3804 1300 1854 2000 3164 1011 3732 1563 557 3880 2802 1921 3889 1980 2890 297 3006 2352 401 1924 2750 1389 3250 3879 1909 3952 2171 2458 3148 941 3265 122 2293 2862 2152 2487 2687 3838 3829 568 3005 3366 3814 3558 3438 1199 3515 2309 1362 899 3895 2754 2416 324 2852 1734 2946 3666 874 1299 2669 182 2566 3392 1094 2715 2212 3104 561 3536 2228 2146 3910 3226 1297 2830 3309 463 2468 2940 2395 1886 1368 513 841 3479 3645 3344 3770 3312 1202 1237 1627 2755 217 2001 1271 938 2845 2034 82 3909 2387 2996 1443 2697 1045 2506 534 1460 2072 234 830 753 765 1352 1584 3035 28 2966 3234 2400 3473 3897 2734 2493 3631 3108 2108 3509 3984 1429 3758 2937 1357 439 2117 2550 30 131 236 3961 1063 384 3714 1374 653 1177 3174 3815 3437 3215 1636 1660 754 3122 1012 1347 698 97 129 295 3308 3183 2213 3047 1148 3484 2290 3210 1576 3134 1018 460 3561 2533 1466 3398 112 3142 1769 3606 2617 3348 769 3772 825 2593 1597 3832 3828 3028 425 1954 2420 312 1943 3620 2177 3507 3342 2530 1622 2260 338 187 2604 1554 210 3093 2092 1537 3140 1262 3834 3297 3231 3727 3261 3514 3863 3874 3307 532 923 3369 1672 679 716 3326 2235 1294 2273 506 2048 548 939 2656 2767 3725 3323 3129 2027 3891 2104 2976 279 1092 2081 3597 966 1067 2329 1088 3936 2875 2359 3505 1344 2736 3445 2206 863 2895 1768 3281 3182 120 3413 3393 2484 90 2927 1857 1972 1718 1530 1735 2344 2415 3303 500 1521 3604 3773 2535 1792 381 2779 3513 882 3120 3156 3760 3232 3032 2730 276 385 1853 105 1656 2666 1206 1404 423 2563 3489 136 2546 2237 3825 935 1667 3136 1056 2256 634 802 2762 2032 1473 1013 1916 1840 2801 2311 412 2385 1349 2842 2097 2944 516 3044 701 2370 2051 1383 2443 3914 2053 3492 2266 3280 1947 449 943 1134 828 15 3296 2714 2993 2759 1155 1783 1198 742 484 3579 1113 794 3717 1043 3022 2298 3416 3894 2105 3290 952 1293 1064 3877 1165 177 789 2768 3691 3695 2079 433 1822 2560 671 3080 2807 3503 1520 1679 1416 1200 1133 719 756 1025 260 1880 2900 3160 3549 3979 3768 2812 2128 1395 1516 3927 723 3208 3079 2994 3712 337 1550 2161 862 3424 3957 315 1931 1053 3193 3566 3320 3723 529 2470 1942 893 2334 3753 242 1387 2323 3074 2963 526 2708 783 2860 2010 370 3106 1759 3848 3663 170 1315 3843 2196 2103 3576 1263 2784 270 1856 3795 1881 1008 1040 2139 1495 2626 1937 1610 327 2701 866 3328 213 71 93 454 3314 2519 3660 1448 2587 3045 3571 2312 3221 3113 958 2894 3163 287 676 2624 3859 1090 3841 3404 2941 1487 928 3318 3466 1871 2337 2785 1358 2594 1093 727 1515 3824 770 2631 844 2619 3788 967 2430 3564 581 3087 3636 1648 1159 2627 265 421 906 560 3524 3898 144 2600 2225 2745 2219 2625 1078 1228 2283 3724 161 350 406 1475 2668 1418 3559 480 402 3239 3159 3731 541 2258 2063 1579 890 1514 201 887 3190 3689 1214 505 1690 1173 2684 2191 2698 1742 2031 3785 57 3893 554 286 185 1602 309 3060 2288 3941 1192 2379 3734 2082 2100 1060 686 1462 333 3917 2437 2781 1167 3464 3867 3976 3715 2912 1408 3754 348 2473 2496 1142 3422 1336 3849 629 2607 3385 1269 2686 1803 318 1074 3693 3249 2276 283 878 2249 1437 2462 543 2200 1026 1492 1917 3223 3951 623 3523 3085 838 3665 1923 895 3384 3812 3610 2153 3322 2823 2642 896 2116 3517 2308 2814 1485 2085 2431 3161 364 3955 3097 223 995 1332 3971 1391 3056 1143 2486 1828 1420 3418 66 1994 512 936 3082 2262 2577 280 2183 3776 2925 1883 2592 3374 1987 3915 3884 73 311 320 36 2205 3594 373 1749 3741 3878 3844 997 3683 219 707 3453 451 63 3001 1623 839 2450 252 490 1435 1156 1658 1267 2982 853 377 601 1888 2539 2752 3791 855 2120 3885 2727 46 3121 2850 531 1815 2347 523 3420 26 3158 3187 818 3892 827 3698 104 820 2348 3842 3188 2362 1997 1743 3213 1925 437 2406 2176 25 1254 44 1449 1519 1453 1898 1698 2652 179 3573 2251 951 804 728 3336 125 932 2527 1903 1731 2192 607 2872 1682 3978 1982 1877 118 1522 1140 1354 2150 1085 1103 3212 2828 345 2720 2485 2922 3463 800 2268 2060 344 2118 3713 2195 1772 730 1862 2844 1411 1956 3026 3481 299 755 699 1748 3109 167 2950 2804 1379 3293 3719 2248 1468 3643 1239 491 146 1802 153 2156 956 1740 2255 343 2411 1766 3653 3259 3792 654 2681 524 1940 2929 382 3112 1353 1377 519 2985 3145 2451 149 937 60 2320 1771 1790 2645 3528 2947 965 2444 1590 2542 3020 3520 1250 725 3072 3650 632 2062 2303 306 1843 1195 250 1445 2390 786 2930 2280 1256 840 638 1788 3247 203 3901 1595 2939 1227 2184 1892 2924 739 24 195 429 957 1741 2061 1319 3414 3199 1350 3469 606 2345 927 3131 2967 3292 1005 3194 1534 2820 13 2644 1076 3019 38 2743 1160 1612 3216 919 2556 2691 173 684 3857 3275 410 1497 3273 2046 498 3556 2792 741 621 980 2121 3441 1413 2138 3911 1106 3945 1555 795 3116 2778 1210 2321 2777 2585 553 1486 21 3639 3688 1203 3167 2007 1615 872 2170 3228 2717 1536 3115 1807 814 3207 1906 3062 1846 2601 2495 812 2811 3011 1150 572 1708 3381 355 2019 673 3918 3321 231 614 3972 2907 2703 1068 1276 197 1710 3574 2232 824 20 3677 1493 921 2241 1817 471 1678 155 559 88 134 2194 3837 3800 2035 1599 3255 907 453 1193 1275 362 1606 398 1137 1044 462 3506 2422 3596 2854 999 1179 3451 972 1427 3658 1808 3692 2744 3545 3655 767 479 1946 1512 2614 3920 1499 3127 1229 1611 2011 3696 3906 964 3095 3612 3465 1122 3939 908 1961 1422 1392 1588 466 2723 924 3143 3317 948 386 1544 2575 1756 1836 331 1929 3049 1116 2111 3757 3626 3491 1763 3313 611 1848 2384 685 2076 1457 1724 3377 2909 1689 1301 1232 1561 3784 1481 1504 831 2615 2921 1578 1394 1360 1323 2376 2448 596 1351 3554 1020 188 3738 1721 1417 45 435 2131 1641 495 2518 1635 646 3510 704 1896 2938 852 1778 672 2168 1608 2162 2436 2129 1285 547 1337 3192 933 1913 1338 1775 3425 32 2818 3472 52 1650 1621 444 3766 256 3720 2992 1533 2059 710 3061 1455 2739 2559 290 963 940 2364 1257 1465 1524 1596 2843 3003 3295 3617 3630 2218 4 1310 1546 3587 551 3088 1033 2197 1476 764 3769 214 3950 3786 3928 1640 3796 3494 2403 1773 3402 1638 3245 2522 1059 100 141 2244 884 183 705 2935 3102 2090 1620 3823 1800 1696 2707 2968 1247 1548 2603 1551 3872 984 1244 2340 2008 264 2534 42 1105 2151 293 2015 171 3378 2404 870 3417 1543 2665 3674 2397 2841 2918 2246 474 1388 2211 1328 2568 758 3110 1290 1009 186 3264 1163 2002 2772 2771 556 1217 1421 2425 2343 2233 3871 1985 2317 2203 3311 2840 891 2383 75 3084 3904 3913 860 2045 2182 3850 947 1261 3710 2578 2326 160 2902 1038 848 3899 2408 3501 3256 1776 1569 636 422 2864 3050 2399 3447 582 715 1874 1161 1086 2355 1564 3277 1745 3286 2208 821 2227 137 3448 732 1900 530 1171 150 650 584 1265 2333 448 2432 1963 3304 1117 3916 1701 3446 1415 3747 762 119 1887 1984 1535 2955 1842 2488 23 2295 897 780 573 3708 2545 1031 2407 2378 2800 2981 2083 2553 2972 1872 2481 3627 3007 2492 2584 3475 2881 2571 2555 2998 208 2914 3361 2401 750 2071 708 2482 1717 583 3975 3963 528 630 1814 1738 2873 1303 3461 3819 1665 3406 1685 1096 2573 3042 751 3443 2239 2296 2440 3176 1566 1118 2590 3198 1726 363 3117 2882 3331 2567 2285 1072 1439 1882 1334 2761 2054 2586 294 2589 2704 409 1532 3412 1683 3962 199 3568 1870 1370 1752 2724 3789 1274 1637 1158 3027 3942 83 881 3456 1705 3462 2091 2616 2834 1007 854 3091 2304 3694 390 3018 973 2089 647 2780 3497 2974 2597 2374 1240 3266 2969 3483 1601 1218 3539 726 992 918 1119 2410 759 1952 819 2679 175 1361 1296 2529 1507 156 407 2463 2042 1702 2472 806 2382 1393 1863 1248 515 776 2847 3516 613 1855 2223 1325 2988 544 1478 1132 602 1510 1273 275 445 661 2398 1912 467 735 2576 954 3700 3154 3748 3853 3640 218 1079 291 2341 1781 2220 1282 2099 1129 975 3419 3488 176 836 509 1181 856 1774 889 546 207 3368 1017 1513 1451 2997 1283 1806 313 1794 1183 1219 3233 2799 1975 2336 3477 3177 1364 54 3783 1097 3149 3607 2037 977 501 3337 1583 3096 3553 2991 2663 2887 3932 579 1014 2803 1444 1629 465 1463 2971 1858 3807 1957 332 2849 668 3186 3922 2511 307 2816 2983 2711 644 2180 3009 2640 2521 2503 649 695 2962 140 211 2009 389 2424 419 2371 455 1989 2328 1130 1616 2179 2247 1895 3069 202 469 604 1653 3333 2044 3902 441 3073 3257 1479 3327 3699 2835 1674 6 3852 3310 816 1425 3040 55 2314 1428 702 1809 1057 1812 1066 1624 1241 2478 1410 900 3339 3185 3793 194 1019 2396 585 749 1110 3805 147 1430 2350 2289 571 3595 2979 2240 1948 2112 2368 1127 2747 2572 746 1986 1811 902 2477 3742 2716 3900 1419 2490 3370 2892 2464 771 1190 619 1798 2903 2471 2611 766 1147 3125 3271 61 2965 1631 2719 2460 1010 1541 3931 3670 845 2109 1224 1327 2853 239 3948 2433 3512 3276 2446 431 518 2221 162 3316 1691 1905 308 1058 3054 1953 232 507 811 3128 981 2201 1030 2806 2434 2217 1949 3525 3332 1270 1424 1483 1146 3544 2827 3624 724 2016 2634 3616 2595 1847 2547 1000 1152 477 206 1849 3000 930 1529 778 2252 2057 257 86 1073 3605 886 1785 2581 3938 3305 3611 2787 2441 563 3039 2682 3376 1396 3067 3570 2004 3480 3577 3876 87 616 2405 2557 1711 1469 2674 1366 2167 832 3496 2107 1172 2989 1482 1446 2386 1575 94 2831 1084 3846 775 2500 2095 3172 2306 1287 779 2509 2725 2517 2990 3224 2809 3272 2230 960 157 2786 1197 2173 434 3851 3810 2673 353 249 1187 2489 2299 1431 2018 2728 2863 2278 416 2751 3 610 3912 703 1304 2022 3427 1686 798 92 2226 3036 558 1284 2064 626 2721 3356 2672 787 2286 803 3171 2030 2475 877 987 3285 662 2175 3778 3180 1278 1523 2570 3244 2456 950 829 2322 3274 2033 1488 2442 461 3973 3499 1242 3346 1313 1964 612 3242 1091 3066 706 3883 911 1213 3227 189 3014 1754 255 631 77 305 2160 1767 3771 3502 3835 184 3970 3669 3033 3522 810 3358 70 2377 3625 2245 590 3592 807 216 1587 80 2363 1869 648 2114 2623 2791 3790 2264 329 2508 1376 2647 3118 2856 1605 227 2605 2817 1850 2796 3101 3252 1542 3527 3982 1153 1976 1633 2904 2426 3934 1695 3759 743 127 1827 598 3802 859 2718 620 1235 1694 2961 1902 2140 1835 1223 251 3119 1331 1343 132 1642 3021 483 2923 3662 3498 910 3831 2125 833 2659 1138 3821 2515 3598 2036 1498 3396 1245 3355 3816 2797 768 261 1797 404 172 1693 2964 235 1386 3552 1526 34 1230 2040 1341 1967 3750 2622 835 858 640 440 2498 1697 570 1746 1182 1149 10 974 793 116 2222 3526 67 565 285 1075 1095 1558 418 892 2372 468 1894 2098 1401 1286 1207 1995 2889 2021 3299 1 3351 1220 1426 19 1292 3562 861 2959 1260 1438 2013 2224 1309 3364 1801 744 642 2469 2650 1810 438 2671 774 3861 27 123 3721 1168 3836 517 2479 360 677 2544 3335 3763 3762 628 2776 2613 666 2038 1467 413 1991 539 3076 2855 376 1186 1041 3383 3868 2874 3686 3749 1639 3267 663 1899 1751 1845 2499 3563 1585 3534 2086 2134 3341 2561 62 700 245 314 979 8 687 2690 651 1302 1322 1820 3434 3105 1472 40 1553 3551 1593 1141 3287 3728 76 929 2342 1024 2188 3386 3600 2270 2551 459 3967 805 3055 1238 3635 1663 3716 1816 603 669 117 2402 2696 2956 3584 3408 1015 248 3460 2418 2917 1914 215 174 2080 1818 3924 3888 2793 2505 2510 3684 681 709 3349 417 2758 2610 2014 2164 1736 2351 1023 2159 476 578 3263 748 1447 2760 3214 3219 3619 3338 1958 2618 2532 3457 1918 1614 2670 3254 3165 1209 538 1668 1884 1983 2748 815 1646 1889 3388 1461 169 1216 321 2361 3470 411 1572 354 2635 2250 2846 1603 2068 2931 1291 3680 3064 1003 3013 3262 1458 3092 396 1061 3395 3124 3586 2052 3685 1824 2155 427 148 3389 2187 2712 145 3258 2257 1716 1081 7 3282 3641 1191 2541 1508 1839 2540 43 1157 3581 983 1314 535 1201 660 1087 3387 1367 2357 3896 1111 635 33 2958 121 637 110 317 1295 688 3347 3960 3202 2975 849 3765 2825 837 2836 2789 272 165 1720 3764 2315 3565 1669 3521 319 533 3703 633 2381 442 2210 1567 395 2764 1277 3954 1225 2906 2145 3450 2579 3170 2819 3907 1188 656 2829 2916 2980 3981 3870 2765 58 1525 1339 3780 1750 3935 488 1266 1707 3654 2058 420 3648 31 1867 3411 955 246 1406 492 2365 3440 1538 3925 430 3353 2602 1933 3622 3500 1126 2861 3490 2123 3301 2497 2865 2794 781 3002 101 2878 1440 1782 3711 278 692 1480 2658 1890 1375 1251 792 1904 3043 2447 326 2259 3830 1316 35 3809 1549 1333 1659 2795 2143 2339 2883 566 1131 428 3751 1971 545 3782 1907 2837 1385 2667 3687 2651 2629 3150 2494 586 1400 1121 717 609 1645 1233 575 670 1518 2943 2951 3078 552 1272 683 3582 2457 414 2867 1628 1144 3367 2520 791 367 65 3905 2124 3111 69 2028 2628 1730 3211 347 536 2438 3157 3644 3189 3401 3200 328 3068 323 757 2753 1607 1761 2884 1910 3590 738 3175 2088 2528 675 2516 1120 3983 68 3855 1733 1104 300 2876 2169 124 971 2039 3702 576 588 901 857 2936 3178 1441 1042 296 3580 597 925 680 3504 3923 876 3956 2389 1795 1125 3153 2660 920 1833 2839 1107 2215 3890 1434 3168 696 274 464 225 1405 1027 1715 209 1252 763 2190 1868 2821 3647 3533 2538 2558 3614 486 2474 365 1878 2763 3397 1004 3218 2087 470 3455 2163 1433 481 2452 1732 3583 1673 1922 1725 1999 1780 826 2454 3881 2106 109 3637 1034 1609 2017 3203 567 978 2158 1175 1505 2543 228 1164 3350 1184 922 1838 2409 3609 1556 1831 1793 2307 2025 3081 1919 1490 1680 2599 1826 3343 3977 1819 2653 2695 1873 1369 2945 2331 674 2664 3511 1974 2620 2513 990 2012 1777 341 2267 3184 2101 2733 1960 3284 478 3531 2987 1356 2676 3235 3359 3302 1221 1837 1676 3886 262 2639 1471 2866 3946 880 2147 3908 3746 1739 3205 135 2113 591 3241 2896 3628 1432 2393 3745 3735 51 834 78 737 230 3139 1029 843 1757 2582 259 1644 2913 3114 3048 2999 1028 3578 761 2419 3031 2067 729 986 1562 2335 1979 722 11 3155 2537 3681 2833 3433 2198 3260 2047 159 1911 3538 1288 3065 271 2713 14 599 2954 415 1231 2766 1409 2388 569 2870 142 1841 2253 1226 1484 945 2026 694 2056 3882 1559 3201 1321 1577 3371 1573 3540 2366 3123 1655 3493 2070 9 2678 1381 1280 1852 3589 1115 953 2775 1259 1048 2133 405 809 3862 3733 3432 3866 796 1145 3709 1965 2005 1885 2735 3037 1700 2552 3070 639 204 2453 3467 871 823 697 2932 1901 2423 1893 1687 514 3236 2274 3024 2102 3661 1264 397 2756 3436 994 3059 334 2680 2569 304 3399 1760 2960 949 424 2738 143 128 1151 3147 1630 39 1306 2742 2722 2282 3146 969 1016 3602 2392 2127 3288 898 605 2851 1249 59 1662 2467 3567 2349 3329 1414 3736 37 1981 3382 443 2279 111 243 3086 2782 2338 2692 3431 2291 1373 1727 1399 785 151 1464 1502 3405 2461 241 2231 3077 426 2641 72 3646 266 1065 1762 273 3667 1592 2808 358 497 115 2583 1557 2869 2271 224 3847 1194 233 916 2662 904 3375 247 1215 1340 3781 2525 734 3352 2491 1706 16 3410 1080 801 191 96 2261 1255 736 1384 3777 3919 1540 48 1661 2636 1935 745 3268 2683 1675 3621 3808 3144 1050 95 499 1787 392 1403 1348 361 2655 1128 3803 2413 3676 1324 3656 205 1565 1355 3530 2580 163 3820 2868 1506 493 2591 2216 2269 1988 2023 689 1866 3903 3415 2677 944 540 3495 2137 3675 1474 3094 1930 2952 2429 2949 2783 1784 1926 3334 2638 49 2277 1402 1089 3730 2531 782 1729 2685 2942 989 1083 212 1891 200 1509 1412 2449 1580 2166 1345 2327

输出5为：

3988