Back
Close

Bounds

Statement
Reliable experts give you upper and lower bounds for an integer quantity Q, alternately giving you an upper bound then a lower bound. (Each bound you have been given remains valid when you are given new bounds.) How many bounds do you need to see (in the order given) before Q is bounded within a factor of 2 (i.e. you know that X<=Q<=2X for some X)?

Input description
[[numBounds]]: The number of bounds you will be given. [[boundList]]: Space-separated list of bounds. It starts with an <<upper>> bound.

Output description
The minimum number of bounds sufficient to bound Q within a factor of 2.

Constraints
2<=[[num_bounds]]<=1000 Each bound is 0 or higher and less than 100000000.

Game modes

Test cases
Inspectable 1 Test
Input
12 30 5 10 6 9 6 61 3 13 5 8 8
Output
3

Validator 1 Validator
Input
12 19 4 15 0 20 4 20 7 8 7 19 5
Output
9

Inspectable 2 Test
Input
12 14 1 7 6 13 3 30 6 12 3 42 5
Output
4

Validator 2 Validator
Input
12 15 0 7 2 16 5 18 4 8 3 17 3
Output
6

Test 3 Test
Input
100 22 5 29 3 93 3 156 6 35 2 54 6 268 5 48 4 40 4 51 5 133 6 150 0 66 6 18 6 63 5 48 6 225 5 43 6 183 6 134 5 263 5 73 1 34 5 7 6 296 5 283 4 105 5 16 3 42 3 196 3 94 5 74 5 42 6 32 6 27 5 288 5 210 5 34 5 92 3 18 2 7 5 20 6 51 4 145 4 116 3 79 3 70 5 70 6 283 3 65 2
Output
47

Validator 3 Validator
Input
100 29 5 323 4 304 5 101 5 13 5 149 4 20 5 352 2 48 2 129 0 47 5 36 6 53 6 26 2 94 1 19 6 84 3 36 4 59 4 202 3 31 3 48 5 111 1 22 3 138 6 104 3 338 2 53 2 131 6 9 1 25 2 58 4 25 1 239 5 75 5 101 2 48 4 123 5 121 5 136 6 22 2 49 4 70 2 81 6 138 6 50 5 16 4 178 5 9 3 167 6
Output
59

Test 4 Test
Input
100 129 5 104 5 55 1 25 5 263 6 282 6 78 5 76 5 129 2 43 3 81 2 168 5 9 5 30 6 18 6 71 4 94 4 53 6 43 5 34 6 10 5 36 5 503 2 41 4 30 5 64 4 209 5 81 5 71 6 104 6 80 4 80 5 234 6 130 4 27 1 80 6 16 4 59 3 56 2 60 4 57 6 14 4 23 3 48 5 202 5 40 4 23 6 11 5 82 3 106 6
Output
25

Validator 4 Validator
Input
100 103 5 44 6 48 3 12 6 13 4 94 2 106 6 450 6 218 3 61 3 18 5 45 5 81 3 145 3 61 6 202 6 37 2 63 3 43 5 26 3 33 4 104 4 270 6 48 5 146 3 130 4 230 0 39 6 130 3 117 5 102 6 99 2 25 5 48 2 40 5 50 6 306 5 7 6 15 5 199 3 8 6 152 5 627 6 116 3 135 4 24 5 154 2 103 5 36 4 337 6
Output
7

Test 5 Test
Input
100 514 214 1128 95 3420 155 2871 63 3853 167 6225 105 1912 72 796 116 5579 118 8070 119 1110 192 1010 100 2360 122 883 125 1487 229 992 127 1229 141 2044 153 10674 123 3682 175 5621 214 1828 163 3263 214 2587 93 5462 233 2059 137 2130 136 1700 28 12647 51 2174 191 472 126 591 121 6412 66 2029 124 1136 232 1104 119 1909 134 6065 158 1527 230 2318 56 11693 194 319 94 411 87 7538 163 1453 39 284 234 4504 21 1553 108 1007 136 8174 170
Output
83

Validator 5 Validator
Input
100 1616 332 1332 306 6467 657 18027 653 1656 366 14724 307 3681 532 4275 596 2243 348 8356 491 24410 182 5553 87 41955 783 1216 572 6572 686 5833 407 12209 852 11485 476 6877 557 2055 425 5271 274 1326 589 29536 231 1102 100 2170 595 10910 331 19607 672 4267 419 6045 380 69927 572 11767 686 1027 874 4596 151 5099 428 12413 562 8068 423 1648 447 19326 631 15684 835 8173 515 9804 378 9513 322 4793 566 10865 367 3064 224 3489 192 2318 729 4988 244 44326 223 3422 693
Output
26

Test 6 Test
Input
1000 1158 491 11088 277 53767 358 50567 14 1681 423 22631 147 39806 148 15513 419 13228 472 19324 230 4476 122 33460 210 1913 165 16145 154 5758 210 46398 341 1570 149 8025 271 22214 345 10293 275 5421 108 13176 344 6266 263 34761 152 1438 431 32300 263 76404 122 8712 411 34973 541 25388 229 942 348 7790 154 10844 46 66432 293 6973 141 3886 513 109350 400 23372 375 10615 168 4991 300 21702 407 53379 529 16934 356 49191 377 20742 166 16244 501 12763 206 40448 365 5826 463 40340 332 816 350 14795 387 3580 323 48522 119 36900 552 15633 273 57709 308 12249 415 31756 240 8671 34 49489 225 3890 254 7954 347 32779 444 6260 261 6776 162 38502 244 65444 234 6232 262 23675 346 33424 107 15772 145 9456 417 10067 400 4490 475 10760 302 23064 222 15579 287 30002 460 1172 351 4122 334 14061 83 12882 313 45240 512 5848 209 86835 254 993 68 6125 149 9380 290 19958 305 7274 322 7915 255 7911 271 19418 475 7487 226 33679 298 16911 332 8984 310 22347 201 48413 163 37236 306 39384 306 31600 161 17784 477 22201 348 14925 124 24149 223 1144 293 31373 450 8409 326 4702 456 4426 143 11849 436 11417 111 23615 389 8125 334 49586 455 26371 318 45621 365 9770 264 4433 363 7112 334 11887 307 10244 290 4501 318 1952 471 45737 308 9339 590 5781 384 68674 529 17600 377 19576 214 24477 464 14670 240 25560 148 22119 390 5267 358 27352 218 1099 532 4141 331 922 295 28079 263 45086 257 22076 370 14408 122 20203 353 3092 288 68604 594 4035 335 43516 511 14482 310 18373 259 3821 193 3202 428 23860 331 18613 154 14306 385 9953 383 1020 248 17001 267 26733 298 17306 522 35583 399 7490 232 3891 533 62950 405 7241 236 22562 405 20010 449 2576 226 4365 252 1040 495 28223 314 10628 121 9934 529 7983 262 3830 483 14795 496 1838 110 2334 569 5732 284 24792 518 3854 325 29189 279 16672 242 66873 349 835 421 23565 409 37698 159 3427 450 2020 425 1635 305 13762 563 4629 287 9358 486 2223 564 11251 222 5876 289 33106 606 63905 77 27479 287 9008 298 1107 223 11323 475 14583 317 1673 321 41593 244 6697 399 7726 358 732 501 6774 350 4676 170 25231 246 23403 544 1966 393 30393 546 4853 266 4326 242 37436 490 3856 85 7044 581 60290 304 8353 269 5407 198 6734 269 705 422 2086 581 24821 366 17701 557 35106 241 32389 130 3722 69 83398 478 15506 408 767 515 8163 515 21871 258 11027 217 4151 233 2123 267 25076 330 22696 174 26793 185 18985 443 62980 338 29111 373 10514 592 7336 279 30755 423 7765 395 17882 336 82270 297 25285 567 18544 331 1271 367 39289 363 22153 248 52568 71 42955 129 2843 423 17593 478 20922 106 3097 302 20840 330 1987 206 2603 462 2502 263 24207 420 14568 150 3112 166 16577 546 13331 245 40209 392 15085 520 7257 329 684 279 33746 197 20702 169 13815 258 30485 202 8348 246 18115 340 60609 255 5819 225 10393 172 14987 375 7223 367 29000 384 15679 104 16502 372 64628 69 13273 181 36361 206 4879 416 9323 166 7132 320 9134 453 9871 258 35604 123 11439 299 56983 566 16215 51 3914 469 7318 320 17881 178 38713 531 14101 332 89414 572 1839 429 1076 328 713 488 6799 437 32128 40 9194 321 5458 216 64493 556 41292 291 25740 171 16288 446 4029 321 3297 563 38884 488 10964 305 29323 295 42378 369 25690 572 25162 185 13978 193 2269 117 60830 378 21953 411 44177 115 10203 404 97755 232 7975 213 20569 473 5802 104 6022 250 5819 345 1368 328 35372 497 27654 489 5856 539 18140 178 15845 24 7806 261 6459 443 18499 353 34110 188 1037 347 25994 351 23096 437 37688 118 1618 307 26261 385 6424 202 9147 116 5984 14 3871 340 5771 309 23542 456 35502 172 10138 41 28495 264 6429 309 34514 341 1208 114 82903 466 23273 470 5634 337 71534 541 65240 137 3853 383 20592 369 3658 493 10135 378 12635 300 721 271 7257 342 17551 93 4084 151 782 220 13307 329 70622 441 29258 110 3207 277 42669 359 3451 461 26497 241 27888 217 26356 612 1519 503 71130 391 8970 358 58414 464 44456 289 43590 502 9159 254 18527 362 20977 174 92235 484 58275 297 33621 305 33131 399 33648 124 14219 179 8873 347 14694 66 13912 326 12134 345 2669 362 49126 57 7031 414 54275 379 11229 270 866 529 3081 474 34480 434 39562 266 14969 506 12082 293 13267 516 11930 281 92968 610 18628 199 17229 306 8969 420 7945 439 2296 403 14252 484 5734 386 80642 519 36987 255 11213 322 8411 193 8065 111 17384 152 18195 554 26635 594 31950 108 16077 276 43037 474 6160 236 55317 292 20335 333 5747 459 15455 472 38029 100 17188 374 69124 437 905 84 22277 386 6921 331 11048 80 15733 134 8652 138 9234 418 17008 257 1718 543 33324 17 9159 376 15488 296 25792 288 1443 468 44494 556 5299 256 6264 241 3733 333 22697 201 73850 500 26410 117 8079 374 11726 312 6369 497 6181 573 3010 17 1783 210 10108 343 8008 141 5903 344 8925 214 2619 254 9431 350 1898 307 32812 428 33474 175 3372 370 18750 428 88553 186 16079 83 10355 409 5931 309 2826 405 7621 459 66038 65 59824 462 15361 359 13410 413 20772 338 18454 510
Output
61

Validator 6 Validator
Input
1000 7632 2145 784871 3644 312124 1690 356851 5220 20090 1891 135515 5254 208861 2199 57250 1237 303895 2652 143226 1220 115809 872 228872 1409 324106 3093 68799 4529 407823 472 163311 2910 164975 2963 162948 3460 201836 2075 184903 1211 291349 1621 107119 4766 204588 3710 107578 3793 440753 4402 17652 3256 30192 4779 252697 1131 99892 4476 251013 184 499132 3618 346729 2654 205772 644 127647 3027 81747 2719 50404 3344 17448 3597 156346 2064 577554 4474 138181 3959 253317 4268 533550 3055 240292 4088 122564 5360 202946 2191 39864 1263 200264 450 475403 3842 102061 4192 97739 3062 168878 2453 614251 2392 19884 5320 686797 4495 272097 3723 41492 2515 153893 1829 359118 2352 44211 2545 210136 1535 138244 2965 195329 733 527368 1459 71683 3799 113337 2379 209592 4863 98534 5946 78560 4016 316084 2616 129315 3320 103021 2512 30122 3410 322137 4385 264349 5204 182332 1134 12694 5746 49247 2689 170397 1197 34240 2642 142015 3859 352376 3892 47171 2731 82946 3439 48774 2445 118059 2465 18726 2139 109887 2987 843206 2531 428554 2404 62081 2915 72886 1694 443606 3513 472089 3172 109566 2847 134493 4427 51278 1942 151525 4355 58526 2513 99019 3905 445693 3129 451437 2593 417331 4511 236162 3149 30382 3956 93781 1771 102470 967 308454 3743 55241 1828 129376 1580 80463 4101 96534 1730 232079 2190 313463 2895 158157 3561 359081 1499 192584 3474 6170 3536 35378 630 258169 2193 179406 1816 96535 4250 278287 3308 76358 3629 12182 3256 24755 4373 88318 3501 190838 3978 20627 2947 19950 2767 491868 1481 250164 2264 470701 3428 79916 4288 28104 1747 352898 2333 82379 4723 26639 3824 243740 4094 35767 1151 163440 880 116191 727 482474 4808 19618 3171 554930 1729 127571 2007 143688 2412 307346 4859 131976 1268 84716 536 111951 3771 35065 682 49183 4223 434331 977 272482 4356 142297 1941 71097 4112 78637 3018 67580 3118 489944 1481 187720 989 205140 5063 467723 1720 91788 5837 99618 3692 760071 2675 39790 4483 25400 3984 256496 2766 106377 2771 95556 1621 12961 2226 352661 4802 126476 2260 10615 364 321744 4186 169060 4195 165472 4876 109168 3068 65545 5584 142895 1999 171504 4136 114084 932 126898 5483 336572 1560 42431 1809 145317 1490 631302 3390 72824 1826 151314 3856 174937 2594 202909 3076 258154 4340 111383 1620 45226 4810 83298 3490 20049 2870 129889 3871 135926 3913 34224 3545 538028 4025 149010 1394 272914 3678 157956 3354 19846 3779 647319 1228 187286 1315 177131 3500 212672 2289 65229 2905 57907 4410 48004 1228 61150 1625 78778 1925 770016 2572 65547 2816 692543 5300 176701 3798 48523 3018 482425 3529 36323 1898 344600 2504 79510 2372 99892 3637 500618 3354 25472 3374 244076 4568 45628 5404 788649 888 192000 2987 211903 3927 102303 960 70378 1789 108342 2319 72193 3153 210014 3096 78386 2617 180533 2966 23413 3812 497964 2564 666565 2589 30139 2644 116627 3622 21104 1755 152690 1395 139711 4897 155454 986 201571 2300 162415 4005 230201 495 19979 1592 281024 3096 138135 4639 331066 3747 148211 4732 57647 5880 282304 3412 11839 1610 921238 3234 417832 2381 317494 1117 12601 2239 122380 1344 87611 3549 590766 3001 138538 2680 377709 1918 441011 2184 199071 3224 275481 2592 88620 2801 64198 2137 433686 5378 31765 3573 136942 595 70650 4300 140853 2799 39139 2631 172802 3617 16304 2151 73947 2545 80152 3718 43540 4705 13555 4215 172001 1259 284622 2387 966262 3066 133008 1779 101199 2357 67061 3680 284139 3007 39635 5149 408245 1812 181636 3434 152991 3403 60510 2965 62220 2720 49770 1778 77558 2704 187621 1675 32369 3102 28077 4430 283770 5556 199859 2406 248608 3268 198175 3866 39904 1282 129210 3060 1010125 3273 55240 3796 40940 4510 458236 3185 11040 1792 14785 5380 125078 1850 280882 5466 124074 3483 407142 1791 110879 1491 358427 2630 204969 5557 144336 2388 138589 2494 114865 2145 349246 404 17069 2494 1044524 4574 115100 2597 61586 2297 39740 933 474551 3490 213455 4290 8797 3783 728104 1131 153387 4173 621129 3261 392938 1689 75103 1973 632337 4108 98643 2544 53477 3040 290836 4951 185169 2602 83362 445 25046 1582 413291 1691 210326 1974 41345 2166 55209 1062 215984 3991 15397 4737 20747 4430 340032 4279 274138 3382 89756 359 84103 2665 381510 3354 167522 3992 11084 5529 110965 2258 85244 5754 170151 2298 61872 4904 120635 1442 71583 3878 105023 4184 63936 3515 228464 1778 202276 2012 27515 3222 156412 4130 41066 2157 178317 3745 199501 5517 346747 1123 194242 2604 87690 4524 116685 3440 97986 1260 36573 2605 115956 1009 130225 1158 156819 3030 453420 1898 25850 3606 43525 2678 46694 454 114993 3249 16879 4859 165671 1029 59297 1367 556039 2216 292272 3388 265731 2580 112613 1780 113486 3547 86189 1717 80750 1863 682366 3450 731313 3790 91278 2062 146673 1547 344062 4232 58026 2103 215062 4095 147990 3374 182939 1340 116572 3637 346013 3322 128506 2912 215840 3064 84956 2587 245602 3634 279784 3041 520318 2599 72783 3575 25167 1062 538327 2597 25646 538 32932 4559 8722 2925 73142 2864 87994 3085 45911 5864 404668 2176 429200 4943 170755 5193 347150 4530 42862 2956 96146 2105 116061 3128 564951 4109 120871 2490 23926 4287 17634 3818 85794 1153 75248 3960 732959 2931 169418 5463 112440 1245 710044 515 53310 3677 48935 2707 127622 2428 146068 1318 7753 5432 25449 2936 80898 5546 228922 2780 288923 4252 198048 2071 536289 1888 79608 1866 251523 4898 70011 2264 200087 4004 230895 3936 20462 3306 90738 3843 413305 161 452059 3360 62799 1252 249585 2396 161665 1405 756041 3105 84864 2355 72942 2247 89838 3067 108864 1297 403362 4727 24072 2826 10130 158 73417 2181 78985 1018 24660 1889 22287 431 124395 2370 57485 1205 115698 2440 470318 4804 154326 2052 83121 2531 178968 3749 17235 3134 331973 1943 6862 3739 133417 4079 169346 3101 83259 3165 940677 3536 71563 4511 18628 3910 279479 4878 120238 2476 92307 1748 190378 4953 143852 976 40589 3030 20964 4449 467606 3641 215673 2893
Output
8

Test 7 Test
Input
1000 1390260 1335 238525 666 408832 1250 512109 63 533435 280 418767 1594 177451 1494 745503 1094 481481 857 223800 857 800371 1786 339840 1615 1404382 1599 665486 1023 397393 1649 253648 1444 354620 1220 769025 671 504762 749 1269210 1085 978795 646 324937 639 4654 1135 287206 1573 1889080 343 1931458 1618 323708 1150 197766 694 86917 1427 1040561 1322 99066 2064 31782 949 2466010 957 792290 2199 1222226 1144 342436 1327 200014 1408 340181 645 525066 1505 1414850 812 97618 822 446951 1507 234802 1189 331916 632 233085 578 101251 1830 606550 1628 612424 1823 637637 132 727838 1918 1084167 804 914716 1896 145114 371 487101 1648 486972 920 595281 1707 182622 675 662782 147 703476 1155 1111025 1725 681750 2009 35706 1381 841124 454 438241 574 153104 167 35347 398 1079308 1780 499269 1356 849742 958 11694 1277 3097455 2032 275121 217 791475 1291 454025 833 1560344 1898 1054342 1405 157024 2213 8768 1588 1528887 935 508645 1735 208220 1172 969507 815 73550 868 139174 980 699179 1656 481003 1348 306861 1169 326299 2081 45128 948 1016635 678 1451209 1503 11132 963 254785 2091 1650834 1817 324693 117 543210 1562 728674 735 771740 2150 1552951 1852 427884 2289 130471 1109 426583 1115 567835 1316 1961761 1592 399966 1896 167576 1229 611261 1023 367178 1712 982641 1254 721447 918 340680 739 66455 1288 110490 966 48007 1369 82823 1171 485297 876 2484308 1581 1506829 1436 97273 1063 1109947 2180 103633 1209 581861 1114 569170 1994 610735 376 103032 1683 1270589 1618 1030209 1318 221590 1216 57324 1198 1156880 1279 396785 1918 567707 821 187288 824 1249663 1178 27378 1375 1482458 563 537837 986 224604 2087 1981522 1786 1077345 1018 750706 900 132863 1585 434329 1938 1574167 854 882801 1204 601430 893 154298 925 697104 1170 964280 1147 2168311 1746 329237 1459 219831 213 1069260 149 1113872 1286 1530250 1098 442846 1765 567956 1260 683254 816 114815 931 118239 1497 192674 859 2011798 1568 218288 1359 942871 155 511765 2049 473673 637 607946 2022 105328 597 430205 1443 299377 1808 463077 658 774509 363 2672013 665 189846 1361 598468 814 1052307 1664 457089 2136 523913 1040 8448 1536 425309 576 156316 706 100122 1003 620108 1024 293088 1349 260710 1212 40527 389 407272 921 175189 1442 3956327 639 1126743 951 168307 1496 1127332 1086 158680 136 1976631 1164 157071 821 211071 1581 318522 487 447400 1516 451563 437 251688 1253 390698 1060 970008 1437 32051 1763 4304973 1775 1107686 1788 1861498 1736 120389 724 782818 1737 557620 1160 1008909 711 529158 1002 116036 974 52215 1160 322647 714 1431201 1043 194791 505 324672 503 1136109 644 473815 2024 2680 877 226055 1152 2653003 637 1721322 1895 1540058 1561 424922 820 417723 591 320882 1181 281144 995 968421 1565 215456 1441 159868 846 253498 462 623634 1336 359317 553 1195195 1055 419122 448 214104 1247 405057 771 2646 990 59108 823 267034 1155 1676602 463 283999 411 436309 1457 410089 1385 416871 1138 973364 1336 363785 1421 121715 847 827709 1120 25073 857 133680 853 777405 1548 465024 1082 1075351 448 787292 580 557012 167 944736 1471 940618 1592 731940 1270 130766 1465 487812 1356 712275 669 395044 1679 946894 1487 858045 396 844950 1749 1184268 1303 253906 637 878927 1296 466791 1341 626943 1954 1014712 1137 1123567 320 103046 1013 200962 1262 454511 808 2261715 1042 111042 748 358136 895 588187 1347 581939 1181 49051 1765 898367 1095 281343 1223 653650 887 980228 739 284659 1111 223389 1836 794611 1859 750492 2226 1406307 326 589934 1131 121955 724 246157 510 144647 942 182124 834 561620 1206 252287 1469 1629069 1293 1524225 685 126504 1118 117275 1629 673443 557 767309 1486 2804798 1508 359697 1311 762485 2130 32623 368 1597624 2024 652920 548 745118 1853 487742 1195 467863 1936 397519 2048 382250 1791 670769 1445 1246088 1026 598341 1293 513961 1138 326980 1911 2067444 2026 1359617 1074 2244557 1496 847718 821 438715 1250 732091 807 549019 1025 1359773 1500 1257136 1034 375556 930 1645043 555 107357 987 577894 1208 518986 1215 1007805 1087 293995 1293 1042537 1263 143412 955 1028070 1392 3447999 1874 869478 1517 18443 530 896446 1106 782618 1162 638868 1626 392835 69 714818 639 727020 1376 85844 1156 230700 2066 599343 806 2408549 1211 701238 947 931359 689 2408 939 130840 816 417373 1567 345194 1548 571607 1425 157579 1868 130875 564 203212 1365 1296402 1988 4188438 384 362204 919 1014156 1175 1347707 457 1144069 1145 643731 1437 949840 1696 690715 1426 632360 1183 60996 1617 1485960 1527 12006 814 1872409 798 292837 1359 182449 1386 1592670 883 1948581 1548 599128 964 898890 1504 556737 568 1002649 291 997422 787 1358270 1472 4365415 1226 1757986 1007 263978 835 389581 885 124966 540 72391 1261 208835 789 86864 774 36245 1771 665283 1919 520929 2160 890127 1139 1071573 952 353878 610 258135 1216 1259520 851 33633 1318 101125 1075 12957 1512 178462 1635 376655 2268 181523 1390 781270 983 1125881 1294 492881 674 8269 1538 821426 1382 408119 919 542649 1381 497319 994 2220961 1673 1638213 1286 536311 1358 1072117 1676 1057672 1220 2110489 1846 386093 1290 398272 1285 1079538 786 415370 2213 1666196 1267 221177 2160 299374 595 13433 994 712832 950 1792900 656 1668576 1536 474860 1159 347311 1937 524707 686 555572 1027 560489 1061 1697101 878 5605206 772 63527 1978 8555 829 245205 693 657155 1288 1606583 1071 140619 512 108955 968 769322 1196 304134 960 24345 1163 1028700 169 949391 332 1190744 417 1343332 1572 1979626 1830 126706 1537 1477242 861 1281548 1786 2622682 1015 715798 1416 633936 1418 962682 1322 94261 1260 311007 1669 647644 1914 1077691 1246 833085 692 650127 1235 245551 1775 443608 976 766960 1090 15573 1043 1209436 910 1890066 578 1973073 882 1168477 1713 819820 1636 309145 1052 79196 1811 85115 884 18902 599 132780 1194 1209002 1229 273916 2269 157219 829 606871 1156 1513352 1658 223738 324 597010 886 270203 772 44813 526 1333683 770 993846 935 214410 897 1468546 833 1172395 237 205713 1803 70714 1006 253811 1697
Output
439

Validator 7 Validator
Input
1000 92494 2139 2601185 2375 2845981 3980 88513 2304 1701097 3042 8218411 281 1926571 3569 266262 2994 607782 2765 3657600 4808 902978 3650 2092825 2920 174512 4321 1978865 4014 1599343 2204 774389 1245 776167 2574 2031444 960 2356139 721 8768750 2181 427203 3729 1778894 2712 1532059 2477 5911749 4186 46899 2295 166454 4839 5459930 4491 3138376 3230 3952314 1438 401938 1559 1220614 3071 5162374 2417 390072 4242 458299 3123 1969895 2087 845932 2996 327355 4218 1027496 3926 3636555 2549 2073370 3172 653154 2717 1317761 3225 234067 4811 2634976 4876 2093005 2906 2890677 1728 1921201 1556 3271476 1765 3019515 2832 873631 654 27301 3158 2164827 4741 193761 3202 502983 4514 143285 1558 1020558 2606 1084041 1659 5974165 1918 997963 3574 7016008 3169 32640 4891 148576 2858 77099 1570 1170598 4042 647473 4407 10398684 3630 6581697 3354 2212267 2060 1065653 2945 1274760 4124 291817 2756 232905 3145 1274214 4546 94848 2543 117024 3333 1593871 3853 4510861 2391 579075 3110 1127284 2626 675282 718 160321 1204 1602808 1050 6592460 2200 1918806 2287 3895865 2570 1110352 2773 7908667 4198 1826618 5001 327893 3414 1247532 2617 3456746 3128 975125 4074 3726821 2854 1139501 378 1913383 4519 1025679 3422 851299 4090 1607966 1108 6449481 3492 2435190 1847 1373137 5304 904324 2502 272101 4116 3683269 3429 412000 830 110734 3493 3696823 4390 2938698 3499 4867429 2456 5302108 1225 265530 3872 1952573 2174 3488789 4812 2375828 2383 658298 1849 275591 1621 582775 3978 1098388 4042 1413009 1262 170002 3291 79753 1807 2646347 1619 1568430 3445 4411026 3536 201764 1959 1099127 1174 242006 1307 564260 3343 2977072 2676 391145 1799 1239635 2094 448653 1489 4643707 4951 877119 1568 1130665 2876 1271166 3601 461593 529 1165253 4195 4065329 2055 1184361 4182 1394987 3803 1397921 2326 645366 3357 610161 4641 434931 3851 3520931 2483 694079 2786 2778811 4228 1697328 2743 4879799 1851 2770089 2971 4539371 3791 401149 4530 2837627 1381 4181122 433 291953 2108 409365 2959 1755315 3348 2323824 4378 207740 4823 1315645 2715 1178698 3435 2061154 3061 6463744 2187 5431541 1823 40112 2921 344837 1693 1617279 3652 457146 3506 1796872 4501 3925554 2655 1251086 1987 475500 4318 2553910 4762 351116 2516 437004 2341 1572283 1942 1639865 808 606998 2166 926971 4558 1219696 4098 1164426 5067 438797 2816 1777476 2685 1760901 4897 9573 3490 3359289 3205 364545 3528 1104195 4712 2050420 5358 204286 2860 85729 2118 997263 5027 247348 2853 811575 2260 1332908 3635 4907531 4123 1192805 3389 25731 2478 1920245 2989 1132938 2876 1015821 3873 1984008 5303 1152912 765 2010190 3800 543903 3913 1861220 3896 647191 5433 4579227 3216 587572 4122 1731581 1516 2365160 3513 344864 2776 1203208 2580 1524646 255 4359504 3541 4960631 2738 4724992 636 152901 1093 652854 1824 651004 3084 4732351 3571 1108674 1611 142347 2509 108351 3064 2354226 2660 2229348 3464 869682 3297 599498 4156 4507497 2792 641219 4990 545942 2519 532299 2846 489715 3202 220511 2138 1181890 1154 3319153 3023 29758 2989 1593375 5043 1129461 3536 1892929 576 388711 1602 1924421 2097 466670 2258 1587266 1817 203812 3615 154483 4652 1661437 4610 3959729 3663 159186 3060 55358 2864 737405 3446 89614 3041 3831437 2506 115025 4004 3006469 1866 2095086 1254 673958 2235 334964 5597 2811470 2769 269535 3711 15701 1708 53906 1423 984283 5346 3072030 2010 1998027 2806 1914240 1337 1073050 706 153980 1956 603491 3126 264972 4647 895984 3560 644135 2336 1563857 1826 171132 5621 87238 1427 1474507 2962 22864 2125 288796 3342 282577 382 803450 4006 323556 964 6161467 3611 1141500 3126 4778041 1728 3826414 1262 6317540 5463 2627905 340 2177759 3567 67183 2225 1811116 2025 1488466 1794 741540 2774 207627 942 8630676 3811 98954 4962 2645183 1683 2241567 2919 852689 4449 268468 1434 432578 4717 1529658 4759 703436 439 4536446 4430 671465 1580 10926 2571 809940 4169 7772113 3321 4532458 5435 557854 4035 968635 2844 1406690 2988 499526 3296 1485064 3927 3709589 5280 1862384 2567 41851 950 2551744 4962 3037730 2499 234421 4754 884255 2793 268512 1894 632708 3344 4622947 1844 1003806 2717 1198062 3634 666300 2692 378169 3352 9523768 4154 274115 1730 501418 5037 2571655 1770 2043602 3859 675038 3646 754700 3566 4626166 1947 3079736 1787 3550681 1295 3614482 3275 453221 5293 699250 3467 119399 1132 352568 3332 1731374 4780 9386324 3988 4653219 1226 83846 3718 46204 2538 1945125 3511 1187269 2557 522388 1820 2512857 3813 863919 3550 661133 3135 476829 2510 218288 2312 529397 4181 2340641 3549 237574 4417 3657448 553 928541 2607 1105071 1984 2504510 5252 301605 3610 1297076 1969 2299677 1151 1924818 3772 1924555 4326 3348450 2512 3657021 3618 1385159 1193 76150 3287 6847472 3001 908673 1891 954130 1410 10705246 4470 618020 3182 4297325 2155 77443 1734 2196901 3826 1157271 4687 3803596 2504 497577 1207 3659886 3305 4161474 2430 3434349 2082 977287 4175 2534339 2926 651165 2644 140845 911 1255050 4510 1701008 2533 2586695 3125 829388 5473 3475788 3175 326762 1786 2197875 5184 297131 2008 7853320 2838 283673 4287 1851937 4398 6588829 3190 150468 2406 1083483 1487 2519427 3687 2598976 1743 1726318 2623 72878 2113 1212184 3655 832511 3095 882859 3584 1682679 4635 105404 693 4843464 3364 2034486 2092 1950223 4217 222739 3054 1021651 4062 1474413 1185 5394406 4819 3642250 4454 639945 587 2876325 4451 176763 5219 678369 3418 1819601 3718 929735 4959 453173 4124 525834 1601 1190031 1867 96718 4822 1813098 1566 2171798 2707 1601287 2880 3181151 3451 1340415 4065 3067926 2337 414783 2632 3681964 2613 33507 4066 2554069 2948 110985 2890 201761 4113 586157 958 7944090 2920 858883 2627 4959546 2392 163554 4557 1440481 5156 769322 2835 480712 1183 1518842 2842 2703564 5091 228395 4761 617198 3225 804771 2838 284812 3826 1309541 4154 326338 526 1698009 627 1110980 2157 4466240 4680 4228977 3455 2491390 3514 457699 2766 1445324 3759 845605 4623 238549 967 2666935 5175 3396801 3735 171422 4488 4060780 4517 3522752 2974 176429 1371 3235683 2880 838770 3331 139025 1153 1851198 1532 205445 2166 4449671 2988 492233 3429 219995 2576 441105 4047 1970705 2064 7909393 2128 4023221 3144 1744110 1324 1888715 2875 1846532 4503 236082 1436 359931 3449 5261901 4388 86716 1217 1994162 1698 407969 3006 304706 748 1012635 2464 10514327 2551 2688666 2695 2357241 2215
Output
371

Solution language

Solution

Stub generator input