CT29600

Amara's Garnet Ledger

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Amara the archivist watches over the sulphur springs of Brimstone's stores of panels. A careful computation stands between order and chaos. Task: Print the number of index pairs (i,j), i<j, with a[i]+a[j] <= k. Input format: First line: n and k. Second line: n integers. Output format: Print the pair count (fits 64-bit). Constraints: 2 <= n <= 3376; 1 <= a[i],k <= 1000000.

Example 1:

Input: 3109 293716 792813 618011 779885 58214 229643 902536 974045 312616 110135 691731 893094 750298 43472 132060 411896 756300 235712 392423 821360 560486 798430 451254 759381 265923 141367 201650 662316 996223 682358 233966 320768 950766 766267 651124 38482 567473 294280 94967 501889 655609 365234 414252 685233 134591 531309 407377 444589 506 490162 15816 188007 419277 171288 538568 471294 511898 923826 21851 337564 176759 291404 459595 370023 575001 163263 715345 110423 569912 111922 824362 705881 330100 680971 34597 23355 34950 851400 688039 925420 210634 852187 765507 869114 856120 539996 409059 267974 914261 864070 255186 627750 605940 958498 500088 796499 637506 274847 235771 466664 397755 902696 639628 986319 449426 394581 404116 718618 678216 851299 361041 344080 649072 359172 929231 252271 883676 391600 391527 508270 761225 864626 439249 270713 566376 261086 401826 872102 774357 357770 537735 46280 451915 738897 265498 72055 284651 771976 882222 470566 306279 659562 513438 910498 338317 310580 174203 398491 517065 805136 897267 456682 800682 504553 420614 495130 148550 666079 229799 667373 727613 755051 643187 456592 661510 805599 639340 115755 321660 779717 730351 844833 11802 443119 220890 144098 571804 200753 870386 41382 722819 22026 601172 182671 926236 166942 32072 649543 674426 602454 620013 426772 262996 284847 880200 381968 801624 700182 658160 952905 732825 329088 425670 316109 812590 814367 222523 971819 699985 880514 527344 871728 809136 444139 477910 867653 703470 256816 787991 511535 102584 467166 627067 919011 495491 628899 461349 305843 639875 587465 802047 134581 156711 670744 916036 637164 216276 853214 277062 254046 735857 128366 870054 867882 351790 182719 657067 905501 250313 172352 289364 875796 779522 543403 668454 190672 970140 194808 790381 883199 953181 785195 821253 673487 937464 334776 209987 733266 571363 748233 254904 926626 307221 460191 241470 925208 278231 560810 941797 559004 940959 491537 432226 346629 748167 761870 639767 907964 172733 607404 539745 475178 812549 788688 281775 447849 891930 442558 700927 461759 882143 51933 810075 921190 806272 453186 577671 257224 802013 655435 388456 387324 620172 289375 241552 817039 105746 278043 552602 330278 429760 51495 374812 919410 439340 966007 628977 829309 261984 676259 978834 184127 849093 453113 3308 258964 726789 857412 177275 853138 567401 244917 745241 55135 676467 951459 646225 919218 341474 411771 17566 809118 712247 579466 249970 938475 21490 251736 813431 281765 33434 21874 779183 201597 80313 170143 141552 144877 891737 163650 789392 652585 380030 811996 908688 417238 130429 594269 380200 290112 965 977268 299876 249856 341180 930151 776009 587787 89790 128052 554517 267449 45881 889974 101653 46238 31694 591792 530922 109346 957248 601244 344615 64153 55092 668644 504242 515234 585675 644981 449591 926998 960770 75392 778327 480716 350975 336109 591712 246023 672177 474903 874763 521990 937290 494726 115469 306036 204025 831711 493738 966160 282225 831739 731850 821064 383198 968102 104813 29759 853274 132225 751407 286275 999509 502639 779232 142093 925767 329582 687104 970985 37221 41068 995510 2515 928675 735012 568804 824363 225689 987780 451283 292880 101105 373067 728755 850493 504910 13334 732194 144797 516059 939063 384066 389955 339767 115734 690320 276586 31816 829671 496511 108545 188586 904129 561558 64493 218616 25137 231844 561774 471450 551833 317732 877953 22160 959826 770029 551934 981984 762500 885838 19415 407322 691661 61002 246278 249920 967228 685018 323299 73397 7459 441676 656163 418248 679650 601710 404797 594973 496627 48498 68052 47749 301183 982202 175579 847295 175191 230295 262880 177973 235543 943903 839424 75625 911024 693374 646090 671898 42896 638598 429131 152295 624953 226288 868343 168653 876122 645784 351711 40594 605232 656505 366348 715612 301003 564182 407694 171404 460182 587378 681887 769032 684199 859462 705735 668200 22562 481907 270670 642843 916777 6570 333517 201434 16412 111111 583384 796924 97212 958518 931276 378928 29641 204204 662440 405246 691565 267204 864187 11401 745028 73838 752145 812519 577802 288807 311 438840 703315 163476 463594 985816 672509 538970 534788 21082 527191 269600 482760 650948 910518 13879 545414 378421 791532 685761 485040 145260 254331 818099 52536 908368 406433 135400 744939 880043 639210 367884 341302 125826 87903 459003 573859 873372 728431 840327 894294 884353 708703 829240 278911 570818 394469 442678 231165 713209 853455 222484 810095 464055 470353 589878 715983 226317 857870 680903 541081 558939 444312 931043 792808 825608 651574 364603 700980 493633 334740 990804 310230 772325 127789 99992 186616 201829 644646 829935 396085 52762 252069 403521 152336 427111 418152 427734 477565 770955 970494 106844 441541 366932 96828 7706 568600 367826 561290 296239 813887 743385 631464 562023 331087 928222 768014 284688 824513 581370 853820 885819 538648 814088 361949 591289 50288 561797 335646 171833 820126 950575 41125 963014 251162 235028 793768 892488 271345 196773 424231 368384 596811 562767 483794 390112 903841 308151 250833 858732 956156 325582 363859 162867 643866 738639 142902 162217 821444 656485 253141 754584 360312 102734 375858 154422 623590 318199 793518 525675 851925 404938 734295 658000 925637 606426 853771 718421 73880 701954 771355 999484 45031 434133 811910 395717 116630 529309 122558 582350 482123 544400 296767 697307 86868 118880 888682 195762 619161 470800 431938 550595 496274 875508 639100 797802 461699 958887 989212 200947 831580 709671 536778 330512 840400 577986 229332 149441 271053 905475 23579 907668 355972 141451 184162 38092 288260 68976 402422 155056 305719 688730 548283 453653 382297 444713 321253 80650 996121 568794 5412 591392 990006 439719 223045 232696 117013 516753 560660 759157 288113 603749 904313 8333 394069 554743 876728 100183 157661 873573 120206 714300 667660 67914 758447 409104 839096 816951 686831 915875 263870 371946 280014 33233 524040 76317 337294 682709 117108 828526 336814 728888 214086 776096 558442 248255 225164 483306 883895 589991 326143 779631 862030 683198 867441 868800 952862 666560 297702 24889 728826 684665 411658 240563 597334 920036 777766 875019 122080 707384 713824 410439 163548 655255 979092 300769 369671 821284 11097 701193 176225 763347 482748 18044 478026 374647 205263 727461 575825 249967 387060 635624 745962 397306 623766 870306 374075 781447 686285 468667 434085 637961 548129 229357 152941 513557 327816 677050 998914 793264 671333 347333 610470 429440 573674 483768 853107 828881 467970 885023 810623 810264 277447 415796 438390 38502 429922 748910 269635 496774 630952 639128 480243 147338 892701 81955 276543 724809 539251 264722 288430 972096 291418 357411 819865 40497 368200 446872 123640 982845 835376 494914 715988 455303 74537 601793 656007 309598 632573 987414 31683 517011 441346 167752 594505 638297 778789 331270 582870 283780 401852 561754 349241 143297 452650 339719 397464 143291 445779 672657 299749 906085 368365 618904 513772 945043 972039 597555 287096 346781 932931 838000 23647 339299 696971 458092 854845 17168 176817 659457 583317 928512 763602 483267 391744 771009 994883 803956 589295 893586 607093 84252 546174 56301 846409 819850 5679 440728 355990 6578 901314 728303 26475 282707 454518 421856 95438 478896 173265 750785 893094 392027 125345 480913 792543 334648 107698 643248 524870 338470 560990 883855 402208 323855 286932 958103 994697 805017 800634 331030 271723 557060 136909 233142 713936 132734 593027 780692 466042 857812 224762 796727 818844 187500 979305 13813 100675 342386 331316 518087 398004 565292 826140 805898 114787 210603 380894 587575 620889 362724 8161 307191 803219 444729 917029 39498 671851 711540 555749 665012 720536 630434 49565 242844 669997 478296 547312 459707 719959 316428 647838 807698 141505 5389 47825 127396 854449 791496 562844 655188 287508 301937 678271 412437 534561 13692 805261 494263 554726 640703 510550 872737 65970 749766 162393 823627 209551 917613 362299 160965 312368 804415 908728 152752 646103 810305 824973 783115 106248 500607 445779 540428 949268 530879 237846 625196 181323 807164 841058 406542 460884 73808 530847 451004 7964 676249 986895 387471 606570 231479 994088 737076 328323 778 846856 65637 848413 330239 545229 176271 397511 500857 531719 626741 592083 965640 304688 942615 818995 966975 146381 341717 727765 995163 21665 884048 123632 827478 186362 592713 559548 202589 522653 288987 628340 917432 541947 850351 311072 727376 944353 471376 780114 810380 369652 649415 843230 514228 302149 386019 976813 117520 232894 629481 999421 49295 755579 984382 755335 827800 114458 632254 801894 945203 281111 378617 268431 420283 612252 62092 319552 137040 665467 709347 250624 992777 484454 258576 758912 401883 791174 223235 419314 769244 288741 601077 375751 163211 941432 965141 364912 136784 749867 932392 392265 693661 559388 864951 53266 203733 10100 519121 348133 905339 809311 64252 11346 675548 123004 345996 89368 892122 481085 917887 782156 125265 88673 496046 756095 315476 606568 160843 475224 955434 99318 773286 283909 984738 769079 117556 586299 705446 778708 149979 92581 443394 578074 826692 513620 672652 771111 944530 782341 940097 62211 235234 133938 821437 258920 580396 908315 389893 572717 157322 2656 1468 488871 852191 850442 652785 443681 919344 64026 732213 992752 552031 484014 346121 137426 359806 23933 678731 263644 642502 343517 253674 867907 372208 998990 116510 837300 964882 253065 631640 599415 397919 701321 254812 61920 676354 705233 724870 658806 573003 475947 722352 761012 122499 859768 147538 762380 256516 699645 765183 214749 211037 592565 762396 906744 339420 444657 864353 927813 88968 771306 35973 239055 946479 714435 629249 736709 565985 127642 227236 359335 829155 661652 356941 757002 88653 526655 299025 471507 89824 156932 20576 92020 809839 281790 49827 693129 952344 800134 997508 837081 266069 817761 668704 579271 401612 861975 15958 617672 304044 44414 842745 304575 470936 172081 241194 52095 622218 134512 378979 317350 480050 552986 937407 455200 539835 249166 670886 195559 995308 308235 968040 696633 520356 264198 136527 373335 863820 877842 878932 743612 762626 546826 393749 996386 831077 896409 934231 391939 307455 281760 385834 887588 188822 2605 652247 541335 283460 980716 957668 887896 299609 213832 937105 11027 326242 106890 147827 196875 692556 872305 304127 978871 107436 70242 590261 191722 583911 962131 387261 998016 936017 222637 511887 554695 746574 635599 456779 144646 125474 861725 47043 171631 746613 141452 730190 854715 475531 116785 188845 338658 674087 986085 751156 734600 21383 876436 916338 491845 397956 890431 104470 645837 213426 23819 1534 406112 586431 221411 874505 293105 911895 910542 903130 507932 52018 258613 519691 818316 375664 141449 503530 698209 886090 712373 708850 736852 989967 920592 804770 55619 450647 255759 399829 101317 85516 734907 841387 898438 67362 639526 625342 488760 326325 433645 216183 690575 179491 65758 316921 581921 467785 148537 846510 858819 308077 315481 859622 293757 379996 523299 821568 841404 322384 498665 112805 899508 555869 501260 787165 763433 738540 548946 585680 548126 751839 44615 551183 347339 814125 780997 938268 110212 751658 312020 28138 369128 649404 882406 457678 996294 327949 440704 820076 718405 75123 890733 762077 56434 106850 191614 961354 644305 622833 119611 49218 942245 38685 470455 261571 534901 456648 462253 602598 42428 287816 668483 179356 357783 621691 922121 687599 627564 821042 702040 536850 916029 629638 199041 268391 443428 640683 906558 500394 93874 750136 283603 7390 544730 471364 816013 477182 621702 720431 952777 185294 768943 34400 79613 930068 925854 431766 20518 492885 750536 141922 928915 193282 169642 304124 953881 880659 434817 293897 683257 942895 611255 237423 218894 772172 251523 517254 48916 785327 633162 909005 770862 153168 218174 398510 620266 570156 618031 322723 631129 228901 344619 116201 594475 330240 450888 257586 752922 651895 361650 388677 24122 714366 516596 627020 407343 60094 572325 288001 290062 960900 956023 816316 989270 315108 419111 634016 537537 972496 656710 419355 158430 519192 409690 723591 532295 967979 203630 827310 404858 478784 690997 861185 44416 933237 264468 722797 249386 960351 741938 932417 355999 137452 712508 266202 746936 95825 632726 861446 914903 434767 682262 797278 918404 356934 563838 80873 399096 14265 62805 503760 642151 538432 670959 928482 867810 530481 198217 186234 10875 956974 658530 749871 463578 974704 144614 606127 775057 883250 623511 953711 643149 962783 213589 307521 130640 619903 791992 522670 102174 810103 389639 754686 900301 666539 67352 36938 229588 231896 787726 367163 79359 807368 702910 891927 714889 521241 551243 29443 436149 806529 797215 449728 25977 693234 283403 496588 480288 683848 847985 958150 583479 123530 395636 351504 173027 319111 982093 626290 288095 650808 853077 929809 621111 394224 630000 459289 194050 470425 64740 150581 375995 406404 230076 634404 656259 904316 399326 483324 317656 173501 724113 908664 215519 717918 188998 369408 360025 957696 19190 531311 193377 903437 804028 24587 620611 767409 314180 395042 358628 333669 677741 431602 117887 479463 609953 645547 273740 356037 139322 409635 800480 138209 93256 523092 399161 38349 573748 482641 816528 692534 753459 402811 974096 149812 869804 783057 316576 437349 752133 36823 265203 326607 322951 524947 845541 451132 886690 891095 56604 633731 16653 930270 718552 104365 738024 542614 386958 529072 723891 74257 379745 603379 862706 325426 830806 314763 830222 799564 663484 871005 161558 970253 592983 370033 575838 273360 183542 284592 845042 400681 836882 732826 227369 624523 529829 250834 453009 123940 847223 56215 28635 104733 526780 867377 37331 50442 262268 393083 485171 98909 773107 929606 907439 329699 435159 229817 373340 594226 500593 633790 187555 590900 362316 394582 83905 772350 94297 961088 198103 293149 957044 390726 22689 356986 465163 934452 295897 541004 770781 507025 900716 995613 870820 320602 482108 99018 40793 551806 28623 750099 499929 912967 670072 361460 493882 892702 196629 710768 312117 310898 43581 364176 256122 145430 144691 98108 459131 776016 892687 147329 163471 930979 294250 851387 92128 819157 770506 732270 827336 549252 934409 995016 42349 534801 679165 845241 776512 826331 918013 349875 944987 290447 912333 21007 30897 919444 716780 42199 842928 50524 454772 649560 972002 294556 509362 653996 495653 967223 745955 325403 710879 255543 764596 462834 529500 620907 581289 226846 275375 478109 311834 407003 614167 493748 130596 592278 580302 740547 643581 984065 359226 278101 529251 249347 496066 756467 783898 178148 67711 302091 166094 551380 666061 491657 215503 885798 299643 885382 390454 32432 214767 325755 301761 17709 966689 935321 329007 806213 974592 16272 302166 829677 357248 184482 606663 734027 726167 619214 826103 111819 775331 128455 729717 378961 911356 842060 129605 560748 206671 16263 693742 801178 700575 237481 37763 35731 445641 826306 428908 645631 61163 294186 62699 328590 691875 684381 302004 270283 421375 270924 929360 262683 265608 62578 782345 4854 834967 818589 217423 402151 453470 817479 571499 659217 177262 667089 881454 93100 223151 299189 321673 16188 969825 721394 147527 976849 734262 804316 216499 389606 766391 708953 685129 884830 539635 934717 328812 223305 494078 243017 374970 76451 375307 853049 522086 833933 972863 729756 752878 423020 916816 564799 590746 817234 259234 438713 731114 164315 634487 701558 937292 97823 234183 976757 192317 373201 45182 874284 796995 387517 963390 109449 341570 274414 680181 113824 501951 935196 299399 741504 585789 143191 674867 951955 252445 866788 364926 820971 929519 890367 649698 441157 588251 845322 573693 30811 571742 541108 361149 888940 75569 145864 460164 547936 299345 872130 425338 634228 375933 916626 386666 690192 675086 939882 517087 328932 66174 191014 558642 997839 782950 465428 140103 910838 561126 174207 676508 699732 267769 287196 326605 822560 861171 645012 229241 559659 806788 846431 943568 974845 14440 743747 583019 478204 604144 390233 500125 595545 609843 120346 182417 867893 485594 265015 164596 206761 801676 113890 256184 847406 950420 538324 115948 317848 412952 837054 219040 85107 681463 460085 273018 47032 351851 989035 218954 280806 944287 873412 617972 43426 176342 863345 823370 809399 56653 506563 16253 465384 164787 368205 818919 218246 221360 740351 848245 982021 142431 847691 96621 373021 33661 11120 493381 796349 785977 218495 801640 526964 912368 782698 541805 142331 184024 7725 626053 242167 715776 140247 766243 802722 430017 889347 154037 414434 915918 844512 343101 200320 647802 810731 560038 687632 287576 529518 319810 900152 78744 482503 241851 686668 228902 379384 480777 12859 676127 734227 342121 279307 465001 904111 965190 959092 172830 820648 361517 287263 381089 436659 751604 462249 89330 310940 372556 384660 493466 54396 910545 80819 408331 896702 334919 307276 509608 318442 329381 533669 270072 170398 335729 583971 31847 556282 454437 318881 931118 571432 3226 673714 583617 324833 646155 996311 667318 479752 509977 375534 645037 592351 349442 410044 381181 640583 746613 829771 361680 972310 498908 119279 959309 993301 321108 30078 519279 15647 973835 468446 683675 857499 445122 919404 574510 282659 317027 963456 989377 248028 626391 241582 418273 429160 834555 409520 286049 278644 219553 626701 511753 447367 829889 162199 845681 13093 599057 29327 319094 883915 635585 707773 669339 356118 346393 396999 474316 880814 525550 783318 911700 2975 991563 220819 137923 318038 710138 755608 348049 644688 934831 19018 421486 613933 669510 298947 231653 442585 778944 135475 477615 559357 499500 107733 397714 787174 452914 777462 370240 954890 247342 540645 149081 738218 602116 274632 14032 140507 771022 48126 135198 462156 889878 605863 370528 214311 498124 966197 239706 782629 67011 142456 850725 265341 220901 922875 167446 337853 951198 691725 851768 654899 626018 829696 392908 51880 246175 452308 203748 699317 215238 694186 605589 448893 215368 808394 22384 981065 212874 625570 726547 286954 429938 183313 270705 486505 230010 528698 277850 394534 915090 135209 895433 834096 733299 225073 991174 21347 205161 207121 891614 388136 431032 288275 260918 39330 627055 831099 399865 95832 967801 813928 448075 742697 754808 956438 947692 626653 865928 366949 875207 952423 224559 188054 262485 621948 807761 420882 926327 710641 611465 921003 451342 897030 85961 869195 998687 684017 459545 430451 243713 970595 369714 144484 36396 474263 65044 239428 432203 278793 839283 315908 243046 534007 848182 709555 460888 561024 549136 600748 127591 265628 215528 99667 428635 812409 523857 655110 188510 533197 657545 525719 327311 500465 60706 153923 109186 173981 507695 320391 514534 55410 781254 929852 213006 113009 968230 928901 687767 936163 228068 486498 768234 288284 657205 561251 669847 114826 886308 461890 797284 996372 725683 935234 553924 718696 990804 283104 318086 166463 804887 854208 365680 164987 307248 414920 779205 343097 486433 203568 924359 442529 829244 816174 193698 941172 257644 611778 532044 236098 598719 481761 770094 785075 726828 366651 882844 227308 584983 205938 953980 448033 143105 812139 196144 798028 926947 976132 883076 854518 322411 6840 376613 333187 666823 451375 38832 614669 799754 99193 877036 234326 524082 188428 850562 58873 598983 890904 22122 662254 376302 971617 61885 211255 901842 602140 702326 955914 319653 399487 948792 801080 237450 410820 897855 181698 732589 228837 908063 397126 786886 171187 852477 96206 488703 925907 316401 717693 853909 323161 462307 146969 628248 519288 166587 781269 461321 222854 890106 663979 665883 160469 918987 84425 57575 93644 345480 446596 375715 488806 855699 978011 83848 22746 260344 840422 948469 374476 812473 260729 332998 54810 302187 352221 387332 113948 16592 127839 168170 447891 154659 469627 150941 553313 604264 366770 410904 998562 17524 972713 495380 932653 740399 191610 347439 575403 572586 680076 444036 628998 234950 398217 710359 849969 997371 676434 251674 644890 325623 79321 929600 360804 806925 748173 770252 115989 941223 893009 903308 712652 258017 378531 186893 28503 887933 680877 193581 445885 274855 523488 282695 452930 496762 851766 233833 191117 852495 791549 621896 310948 732068 688106 473622 664169 354373 848597 583223 585799 746862 785311 719140 579602 200868 925714 493780 840435 436222 432760 447390 782572 183262 466736 876999 740508 931636 738097 991328 581762 186736 600035 461187 602281 812328 273150 257829 804726 68856 920074 427962 619778 156684 568497 780719 827331 660093 914777 983549 831311 597877 766284 989661 757718 874824 656321 412947 701639 291737 857738 684243 632016 533127 369698 231857 875613 719528 487315 15608 898283 414327 749939 817449 472884 131486 124932 321588 528466 173046 972905 629162 850081 256372 884558 107691 593870 827859 439670 998009 290674 188173 204699 71304 185697 208025 173331 190945 354563 626260 573877 841335 84314 949928 242462 116644 776773 421086 924124 132924 84205 976408 709323 571234 316795 12422 174833 81301 180696 880635 520333 274788 756684 930009 88997 866675 581851 559176 575779 283783 826842 247218 142819 418128 913523 967098 459636 928342 906325 42795 273517 42135 745968 991742 800689 271610 398748 344108 308045 882724 469766 243023 184996 140357 20468 938579 142026 272990 120784 47915 163465 59242 748385 433978 26410 514606 370165 372414
Output: 185348

Example 2:

Input: 544 1666757 929223 788097 571484 356130 57111 610459 364666 838556 983670 935055 100603 705049 897806 542869 94894 150611 132988 401005 465540 239885 451757 898599 231007 985054 30169 410260 992896 129076 246630 2023 142815 128461 484700 375305 43673 466102 694109 477590 187798 821994 578909 83935 199439 736365 962442 848988 672941 220364 371541 986115 315607 898944 561585 877490 952134 17723 170802 864813 310540 290355 152124 772806 878180 959247 656289 28312 658141 24616 851504 708016 544136 573527 318786 560123 458843 823860 324438 101323 245685 17676 720466 270658 757589 560815 372757 376312 192332 950587 333976 169649 135559 47453 781793 799535 323306 493966 32497 857092 557296 253215 442189 474672 197311 881295 766280 244549 345370 283092 922822 57654 565307 369563 861998 722602 283767 108329 260285 383311 474568 75252 173866 565107 295792 764782 333092 3784 688213 309840 390765 23076 573908 532381 939019 984953 830516 938101 937661 863979 911552 391118 894470 313406 317026 620020 524052 508099 362697 883769 795125 505730 261867 17239 634312 995373 360990 583531 31986 36793 710066 459014 95081 687146 276653 126057 279239 289370 365612 274514 380550 55385 127111 435314 68277 359510 893549 762323 805450 205630 551709 635788 756426 339929 771721 21241 590986 421665 431062 647706 850931 616763 874930 176293 549109 70857 781959 607220 501457 619239 452245 420634 267153 892134 204255 35992 439569 327291 471118 612772 512975 475992 386458 673444 448626 332708 597384 524768 358527 218610 558207 213757 589595 731462 81743 100814 852775 948034 213486 270495 212212 470018 234784 377362 373465 331710 692582 719642 106785 215694 344764 938267 980019 129502 674513 443289 848644 974728 159009 401264 268275 502517 800053 397786 180994 630203 351541 216001 224595 311950 251292 282919 349970 714313 513709 314884 473406 522772 61450 373913 151814 521649 495453 513740 152330 10864 967310 672690 454969 348447 374495 80343 460527 566312 325112 587780 462998 13849 529249 37541 49489 454049 414975 983520 656045 442611 250796 282037 414467 937528 745150 245476 139942 198311 23511 360819 349031 518725 517026 638631 792751 902626 30962 523506 208601 655404 816953 69310 267467 90915 438042 815518 259519 192521 503556 707426 697888 787201 586489 62244 598309 617515 423863 269467 353421 311349 714955 266127 743986 906824 177959 669292 954879 174716 912855 883446 694273 509942 122714 809648 776930 398097 111500 554169 349148 959187 786827 805290 937291 998850 442894 851572 392741 2437 102012 256734 810490 142717 552715 269020 461725 181493 273940 51351 872247 568141 380160 85865 226240 456299 411323 676292 296952 552181 512868 611198 421697 719895 190023 376062 353411 821546 330181 733193 22060 673088 88026 353729 29904 709822 591127 95022 848264 756918 466178 510213 388387 388197 752972 271299 689108 198743 442912 468018 996309 764606 858404 121372 488710 591313 936320 303100 73663 596510 258416 302974 973555 369497 228525 522190 893723 3145 671006 573102 830084 90033 279393 503565 635969 173241 989582 104792 219081 870750 312999 895949 386809 610853 678800 115487 541779 367219 936940 863166 970882 704783 761544 447961 185064 337233 232465 367417 426650 905452 881483 37323 109657 804842 467701 664310 30089 410474 87849 397212 600722 586303 377314 129685 426252 304942 179929 174062 776301 824181 827358 764725 70959 13574 926126 48331 112353 48908 992550 725305 583238 88692 570522 955105 831109 994624 561717 626307 671078 161342 403405 663067 274180 64282 469627 448713 678085 861756 707549 259121 53361 292228 826618 632288 720969 555480 678824 719046 263732 93612 196518 748757 793420 376364 718129 242245 263109 32247 376687 929283 832008 539364 799043 602283 354885 255757 40330 823978 673762 344213 310901 725156
Output: 141628

Example 3:

Input: 1165 760057 521292 691740 330761 349712 21820 935423 130975 955618 660871 761897 120173 718869 72080 630126 735683 403384 916062 970437 828106 776759 826809 372361 693619 207852 323438 418326 762803 425691 652209 469396 344153 305239 146419 213335 632660 486348 603881 152074 553288 314774 928394 145801 368512 454851 543869 751399 251983 90734 924667 928027 171773 257645 130948 931926 681197 402806 21836 367451 427080 295461 418781 2727 698441 998005 674384 828958 317050 697002 956175 358794 77258 727967 321845 762410 729351 62859 41409 837824 135138 940721 484925 972442 706488 670196 322678 174179 53760 72518 405526 99402 180220 27271 585305 359770 293252 860983 967850 896125 702481 287302 718361 813536 166056 203875 367607 51688 944097 305729 184982 744476 158809 203069 866469 265093 424823 390055 533761 121691 610700 749766 189742 173982 548953 552591 973266 478229 184049 670110 362667 698324 372077 184218 389991 923971 233481 92537 789440 136234 133491 904090 839023 918056 509649 859798 455866 964560 960956 860948 956650 669655 295154 304321 55740 120130 732830 683139 441101 4390 99614 25314 640677 788789 171167 800086 712877 441178 278017 959821 614581 265457 392986 832364 146357 660511 647944 89152 229548 887262 426098 120805 642760 311345 591594 839938 415595 92990 48436 544963 160159 332258 134180 33954 126323 873403 510507 4937 36616 143582 902421 729023 564604 706197 270929 223934 57873 314782 501361 258526 870772 320279 930707 249842 154715 107155 614451 839379 562997 881053 775827 844220 85061 403774 541876 603030 369158 416385 522373 182184 999164 199366 537797 987626 817939 452062 549962 275563 774404 731272 573555 410876 162220 427409 36805 518719 822067 965773 710081 384241 886611 302278 274552 279933 105708 280610 428057 489349 178621 437453 867137 929155 673393 258593 9216 252822 19650 989249 931953 696816 989586 572449 959855 223495 781426 714753 932437 505630 647567 739473 318824 346503 833468 97898 571437 78353 73349 632814 558864 961527 179410 709802 475391 909691 977516 884599 735681 732723 587451 740276 633978 875339 645645 354428 178365 870204 751790 22239 22171 832259 585847 864161 758825 374027 349090 481331 978430 229109 764222 266670 818990 342857 754964 391414 191196 345731 139577 471509 947404 967632 875614 335087 13309 309699 517684 774751 571289 766609 713181 257985 805190 568196 872680 460097 480801 484467 89363 561438 317315 172389 188336 947408 374836 489366 479717 345757 382304 708937 915274 781638 846080 896162 85110 170817 735289 686306 371286 646804 971979 160734 792215 919670 719797 714951 792030 3398 299626 9258 576753 299836 171175 99229 227233 315715 562314 785739 649714 676820 5798 561787 857281 381912 72751 421679 757079 787610 905675 321163 751370 598602 743092 480813 430997 544068 275066 886277 878809 27661 157157 669444 376011 526893 677549 355495 678480 866833 244367 100221 873242 992609 970284 765455 158325 580573 572338 915707 454450 846010 642681 466001 419373 167092 380875 271234 455733 140120 38997 265628 843695 284234 967685 508886 521083 941872 958946 981064 779285 359593 625120 66019 802785 628009 357086 946915 698555 590147 117919 973871 191485 236432 504272 955283 114414 316003 417253 455450 401361 407283 579700 810921 878628 128285 658830 938930 702709 604839 711355 858296 318816 222047 120286 792058 674974 739301 649793 955833 829324 252100 506122 435540 389226 449019 66005 317253 807250 268144 852622 737871 51221 74169 350452 789803 579614 259961 777482 620866 88899 170832 803004 522666 864578 182811 571350 890507 649774 179890 785796 771272 711777 908240 750086 27311 649729 548676 193046 302132 522454 844919 411746 625588 531921 969782 48519 994339 840637 315967 816595 584505 334401 968235 57129 552846 720176 704694 176202 184077 158408 13726 37126 63899 497799 162904 341343 428773 183415 897354 186871 180197 323009 847525 126143 125221 889328 771492 937452 242833 571322 800351 21465 361142 767740 325027 124211 284613 104849 604537 283659 978998 570827 514377 2554 956889 85787 676679 591622 386157 948882 477831 965382 635551 478948 301687 845041 430538 310284 261914 13670 878834 509180 855614 269150 949415 588768 73179 333097 315367 877235 309616 537775 21926 533488 509278 172466 587955 628069 185883 120307 796411 482884 837951 366256 368377 560762 477739 136032 845180 851011 375778 355531 391949 621497 828598 943860 973012 869187 380435 54438 223182 782662 282863 611217 817617 910527 726561 707353 262366 52057 187432 908995 832287 354872 780412 885495 155250 633758 449659 330919 400060 420487 682558 465541 447810 479791 14892 439702 357570 302168 106606 438204 179260 308404 281559 887929 291470 82122 723871 913661 9465 661174 61931 673036 182347 499533 821896 809515 859345 660481 491432 426208 35404 643974 170430 796986 367305 14920 993416 15086 356334 30812 782772 529513 716721 85362 168133 731476 216999 515658 92146 13715 263200 315122 101864 651951 179662 843564 359454 915862 895268 626124 787768 972839 578712 250805 506482 303212 697453 13729 657183 403409 347705 208162 829039 751057 434844 734107 272785 105458 92559 696068 87451 68252 160560 395957 987122 683621 581222 819920 826988 956425 387146 434251 814691 505318 677963 370615 462246 958886 580046 835229 303171 42755 664354 812031 720875 86630 111531 285377 571773 99886 46108 733219 228379 960793 276113 810532 239090 142545 478423 34729 753093 503788 310070 899598 520805 478365 378812 729693 893658 238500 832275 864377 286285 763317 440948 21130 747209 94923 796802 527573 947638 602133 361125 358845 523155 308223 111921 936054 221834 971459 167834 921216 17068 695287 813148 531383 680676 959649 841179 45080 140869 669911 300730 641029 47970 442993 798520 589871 865617 313598 848617 553028 66088 974604 897596 257721 173875 576709 353476 102838 124014 773355 301951 117220 458321 714535 928533 988383 706721 770909 121988 982964 767026 890663 231778 169508 219297 709656 424190 880318 241205 865449 469128 175273 698753 739735 855443 275802 604534 51623 317019 788310 783817 502876 398002 428154 365810 567142 810017 922151 468373 34472 610446 510601 53348 578249 954060 404505 140245 395263 808815 933578 699010 644160 271496 60977 563559 331023 695469 189981 652931 653574 393894 257172 670680 179328 42037 320442 507018 451250 974067 539598 252212 612124 478687 768081 364947 772613 636522 228453 297887 618095 758142 87272 51071 42218 645735 307627 730238 885200 962672 422270 388539 226907 748511 355768 731040 711559 330505 717563 611702 7636 180480 129830 689057 539882 423465 829680 71016 323290 699569 231592 955122 49148 283352 426465 654359 413966 596957 19336 251780 828569 990757 938427 522799 410588 712895 260906 12104 714486 928664 622811 579903 76357 371738 507913 721134 675616 841275 293022 661981 715373 293027 959218 486210 402155 728373 525805 993401 941798 980816 182649 513983 510212 839888 692394 320377 931774 522680 9843 400088 551943 168769 316230 29763 807865 972116 479055 752847 574516 800364 584845 699953 333860 223988 595163 220747 367412 632683 701427 350072 171097 271368 452687 192323 24696 596497 160358 253841 260310 732115 474380 261949 59447 344757 49964 343320 195235 100464 1425 977471 161388 69956 75468 433024 669603 182419 89046 542874 506231 91524 199940 216767 710311 715855 1033 435125 860236 37199 617293 601796 92960 844051 231857 433077 156482 503818 25780 667848 841483 932318 764255 849489 550545 640110 597750 198865 29006 838255 814888 181192 274857 671985 492526 29124 936982 965419 261228 588352 4520 180032 592485 588684 900199 876439 947222 731880 604811 950625 383157 142551 849836 351300 322438 302993 28513 828540 464422 168821 309997 426252 743934 492367 921380 850166 852542 457235 589435 464400 374464 729767 741492 186200 247444 250567 748298 622969 131384 660741 107802 937301 880164 466144 250792 289194 470928 963842 828998 843772 89618 888959 729962 759204 945697 399633 57999 852898 642464 907898 247982 621480 916270 208486 978074 14624 340191 925626 390732 176844 348226 762930 928401 10213 753787 147736 658872 536910 425080
Output: 195381

Constraints:

2 <= n <= 3376; 1 <= a[i],k <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.