CT29665

Innkeeper's windows Reckoning

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

It is audit day at the terraced vines of Grapehollow. Innkeeper spreads the windows records across the table and picks up a sharp pencil. 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 <= 2921; 1 <= a[i],k <= 1000000000.

Example 1:

Input: 831 1601559942 61845673 662972940 787924697 947896080 403453413 781515189 151004421 445538183 439921942 519209529 738666813 345848949 734128189 523544847 601386013 464431443 229906570 931069655 368243561 866262626 160782645 475582456 168196494 905835940 822097597 552157663 609858089 566509188 795891789 84441939 317004269 706947907 738473589 143028932 953518474 266696954 379028970 444662796 994008204 541936433 232952175 168013686 830852728 6449986 525222692 212817835 392574533 464963632 55709505 221671605 161183431 360057 316310863 199582854 11456997 336266197 809993927 602173339 981127543 51380928 804379180 421554314 513492022 664104814 396468084 272911567 842448717 828060230 804397660 199095083 87681095 855821691 642653549 115586593 51792436 61485202 85280640 789309632 976107603 438162237 185398348 231942969 307253448 334146616 745567428 931991007 134730966 497888799 956943400 575453211 670174271 685959903 198355790 139235832 725307135 52074425 220855836 393908056 947983727 912972947 240870156 807607223 328757252 825048125 530097223 679402971 277702037 808786000 978933458 998113252 926154792 275717167 359307482 742712121 824093967 828569910 52437203 94998083 68632341 141593085 394893976 443467251 556462764 960334311 449550257 271847732 23773585 846571281 751231081 430352412 740524185 57446988 184243868 931898934 431179929 217729342 690080677 84095122 714620394 333621579 696395222 22052722 162522277 676240342 348875047 951832442 672271520 513153045 464009332 295141875 543678011 510488620 352430185 93881439 261318284 682806998 577386863 855198372 686046825 951964435 79691058 308505262 801298292 614941878 545473427 106619709 623603044 506767722 606574205 888714444 641822000 733041327 898861440 452430570 898737994 83191837 72663919 795531763 314794316 171952590 378649576 152905421 986227154 71734102 856191713 430532980 206386775 802905699 101142290 430946189 358312333 413456586 900687868 769296163 81255741 773462451 872128505 212817023 60150965 57785769 832491792 967551428 758240355 323242885 201368282 479710342 128237024 63627743 839219388 344188880 380882408 8328459 875533261 121992592 290880241 702998910 559288375 522134187 597158206 382611299 413587453 442958376 577540792 341140292 781743184 54862051 734024711 491601020 43500719 116332487 740508801 915177377 283626746 755833094 900709550 194743704 370806198 108218035 534501497 162364438 346194856 637196176 405783825 964864683 297815039 791417808 858317567 672794388 957598128 860087607 775596990 846718657 225796019 621200932 326417708 793909962 675788276 967727621 347609899 962991622 756294685 73665235 789121924 643208196 193920696 795811688 211565511 185389326 115098223 881192150 688532692 334044104 401947775 574206260 899987158 97661030 172310453 129126863 396882560 867505250 47318624 569118847 782308087 832752672 777062379 797745473 199035056 130745852 458619641 209450380 658023737 871947609 748581932 917629365 657001419 497520977 259967028 268390788 604105749 27785062 26796375 273762925 690072468 709321507 611054740 306538352 363903496 776311896 591181348 203693006 88446884 201959367 491039911 363436564 607723661 852916857 93999198 705510332 226213730 403926387 601221688 640886190 911822974 705521885 183185906 698160223 101443019 472306540 878539919 453695542 767584311 237862087 420767171 787739621 752303761 843766671 64813614 946383424 220910400 895081249 223443945 359557058 295097150 504296795 593260721 95133653 902908485 619972718 325884224 157039153 906376646 123266380 871465879 688354456 646468121 53609379 769548939 624512963 856582678 111431839 93045734 522959413 175040367 939510342 188829077 641437930 467802268 522213840 40216617 423745340 91848563 109905308 55342901 472833898 768794291 334711364 645984425 254646189 716350999 303374505 64551917 128220816 651604920 119380264 914264830 361329021 119993338 156190728 278111620 316171176 501634417 261612024 331491912 605952718 80348095 862579193 974872432 355587651 421851740 845618898 506946064 939390011 540576309 433593406 425714941 187633065 456376871 844207249 790012232 126288418 449427894 995583158 466023384 669709046 60925144 594819713 572403739 85351200 375672096 42954859 5788536 440223107 251954926 765615081 592275423 10832650 699242370 860090361 679140904 56208719 503242423 910527893 210968513 877960805 317858259 482373406 946869285 161993494 899887098 195083805 642836974 944078834 879364783 551285419 218258798 67688925 497796428 314158455 666848951 641900096 49463874 225073769 364116643 283868360 190138953 801585442 91481901 422685248 913870482 944403108 861593834 652283790 253328102 871557850 299448870 361585775 562333711 1589081 573940587 366679361 407863638 342351304 538918851 888211891 941935082 516583673 802186165 139963035 154144421 519218878 310069608 608979961 798069201 153218336 141527121 442859311 159181423 102555128 518127953 167666392 248340123 42067951 983086253 515866607 929178222 244904847 901934637 531284517 570874667 414655315 299134916 495586220 977297928 797643388 392755005 45008575 306672197 846331008 730145735 298665853 217886688 884932188 539056388 4733627 126908287 294364370 737845874 897679428 785965151 461005470 953209177 5766312 824734344 796787275 418553482 149375457 952427072 132768266 516841494 562869983 398691740 941705819 27557856 805520494 41922162 951328508 251185543 467079710 418730604 284846091 954731831 264713968 726195939 349882992 370094187 316531305 184837233 900900293 861972070 65537658 783548116 557277911 481314141 271434212 608869942 188549423 154100732 629554568 521037992 707161124 82370337 89275205 79953866 519767395 873978592 567842565 473565491 41198971 509754656 867286730 432426832 956481042 295194370 41584010 850967970 356464897 221660631 103125966 822635557 672862191 889547048 596733492 737568673 281117266 214495143 396562152 147557888 540786010 49876037 132573679 425986253 904692612 265553715 990222745 127814448 75042147 429120063 93354912 198242403 418374459 59941358 833919620 788209739 978326744 628976935 760567986 29207123 823010202 506209111 409518359 821824100 717936902 193881104 550263789 933520795 91763831 528527968 733916766 175138641 390769844 933767913 189890483 599369051 387680561 504975220 256083158 277674737 614974839 253393732 831169542 181292369 493551118 651675642 698763122 900689426 23496658 874568836 780877023 815999795 442304711 475525036 46707015 313747520 617277101 839594003 438398301 525526773 837137672 514430848 730631647 301824975 795208674 193012557 341981058 939956891 295972545 919818320 626018854 902926939 148046675 356467123 292675323 158437101 213417778 243823839 684416050 492213419 543286329 507233323 66360570 986305689 982874095 654286242 785850565 491878204 993833438 330252641 224927856 340861252 898741211 696576846 365240468 273252966 750340195 676113593 155315468 827810944 779676435 522227895 588227732 576625168 307402141 656870627 803576101 638224775 291735075 11177508 698941103 299232302 842073318 426528920 997087495 587581002 700622456 100059595 986089231 562972364 601102182 975711041 998151012 554903338 828825992 27693827 357793606 545700421 943508115 235152201 617000971 475261804 802707178 568676673 15515942 243092120 923941321 879512140 50042249 141177717 648096545 516830946 495295937 342422082 134588273 194432771 44517766 98083213 118834039 6920960 934833756 261572371 205163116 171007556 163646143 778739164 250902509 13469860 841038699 217686243 106916434 533405350 966989784 609298233 266255489 358308567 190324274 139928897 580728731 578091799 113641687 577409780 432733663 617343210 299392235 603879801 347138188 480902283 429046069 677084924 367025864 879837208 978152344 716167552 894180945 197453350 68737364 402397834 825418967 276732374 678896351 616202036 858026831 661676543 913521369 405731575 205701214 541985167 281461435 733018100 554873740 998127143 224143021 586342339 946969537 855742281 83517719 648034022 130356353 551737673 662021548 102018599 204446422 863509596 162964972 479706442 543285764 102736517 125073046 229952715 656851876 485686606 36399800 332652394 448113846 800374129 358300654 136741058 247804967 708026277 430029022 149331110 306890211 887972288 991619406 208038307 383645248 820699874 821827979 912570198 272724350 726068988 84825522 404907165
Output: 318607

Example 2:

Input: 2445 231580626 9679270 462074840 623419028 660634571 847442049 241136498 613665598 786031617 508965138 610500206 670293183 577143918 45629732 1157775 939040655 261040736 652301807 894150439 978577824 796151206 431059544 624077203 876765644 885492766 851686358 362711740 619159548 275463510 754537442 408921302 38770257 263936087 495051997 778556001 200520699 417174554 837404744 680671117 865051101 652629748 311079091 577009448 82044309 849005390 505210666 892025843 172774895 247896415 598285557 998679756 335795683 568130761 337112452 4515631 846854781 339654615 796040056 370173816 590611046 560806657 180593620 589661851 193831312 799475578 24293641 533151628 179305517 720634661 67505633 81736652 241302814 906542082 490925244 537508334 858683515 8982886 966116250 677951379 345632793 60466327 64723888 535573097 592891300 902260435 499725464 862683685 722756691 323953895 843395235 148863177 821631304 122789947 229270493 468878046 968535022 560547462 347544898 442150896 122007967 618627172 976327240 829992856 661306799 876300972 392322297 681099933 109517112 789720219 785166309 607978028 460658344 426677726 169382099 258068256 81810974 358287434 651927288 964278496 871619796 810482329 707226971 655002431 570195503 144742764 691821395 96017223 216603749 512893024 253961391 968556763 946591740 414631715 872118260 521341208 590969606 367419411 307424157 908512628 677392424 418934010 89906517 782332429 235627582 3918672 324688916 529971120 208381088 789445702 130464140 686631534 54890631 230224185 380556118 633245293 392024170 661073253 40976631 274707134 590958112 203271826 649716252 769094232 872161807 88163066 928021147 717278238 828999312 476736175 87065947 88068667 749737740 868698603 830697389 296955819 666550712 209424909 971491382 911248800 860566042 972787172 997608319 478019491 885376887 814178709 54232235 896659044 118508744 167049948 363604969 736303582 680347183 330337768 900458043 541215224 567029692 600980117 57932739 377298202 474900412 130700 565988026 953687156 722722034 622006777 416360198 860696178 887234946 614970768 88727262 872993203 450993005 562698856 919533019 259704133 876059769 333940932 299001559 573239372 760085775 252493220 488223182 678775360 288312206 49459778 82517285 44102585 610031608 97665982 955620206 536757194 224906757 926096197 801069628 877910208 89534782 380467277 400193350 949959184 304632358 467474768 30940894 779325783 544015631 72868228 850593763 786680996 284668208 653528419 117799480 540253830 381450868 912784802 434381556 27508198 115820048 783925023 79790302 234292760 773028776 118598076 244578655 186933759 389938495 371380934 159115944 885423899 779271683 669700363 809399737 502307762 338003873 87659190 255695924 125780543 728123778 839371068 117888652 205846230 359270057 741575755 288892406 766542766 407985451 626605641 717528931 574887122 733274676 877572678 448761065 42715192 440065239 558328130 857213297 666736778 903068301 561309862 642620591 926662938 994178781 889591912 666657307 731914332 959255198 428758212 114327761 832144420 151673090 892402166 683716657 499195704 383501709 653361925 437758644 206772363 923026989 876060911 836974172 513936586 169917055 569808739 788562415 730566551 911041314 844579471 117437491 855439158 716168477 999346086 770970256 884662726 852287820 601855 571001202 52183851 765973159 754947537 175191886 991041024 821654091 979272239 312864987 416669062 517628817 879218154 414458469 271181063 614621980 221474033 421416303 196774026 860580360 313098591 184691980 776336761 302480441 372495487 266301334 941250637 620118349 465633037 940125457 851554347 201606565 374198070 755049165 613287079 326073027 535307765 43616003 957480802 618384015 707703900 645290939 343132003 237958126 421328217 796105355 144982514 87354726 935425941 3041538 554462347 897682782 322757560 649460799 56976495 855236520 902750057 869867267 676328105 43972036 938208784 384577957 314064481 329185077 893801681 233748979 644840593 980759191 531346762 823382644 860869358 571600490 993653543 265556814 342430549 817290444 993599005 626477643 519329822 391806466 49873884 158529430 396405246 524678134 593544571 894292209 656959796 793065287 392236939 501373820 730592470 798811471 348962985 6906266 565080804 931145828 157309524 194443208 455786220 847867409 827793420 435880503 256675577 456485907 440897361 898596720 646445490 373475924 349183321 701229299 498001886 619179136 950459456 651219896 82299334 8068319 916794557 423732751 817325738 468557842 408257689 539454488 51699075 288548468 155999527 441984505 817324248 589268679 676472464 81051463 685064022 760160915 1300212 158790109 479688228 27449068 838615488 339786616 536406438 224744954 240847039 840387316 514126887 500001797 940136375 846984053 278609839 152496796 558938698 768489254 806429138 153325430 582706602 141655983 129528454 252023881 103753840 540268581 787982464 387060455 22520817 600371331 149441827 188055265 233970595 288605837 106276446 818692418 849766157 426175725 920997991 632911360 467036398 494273306 976565385 449438213 933884231 857048614 363124778 948812016 715703276 85141714 382006349 807213039 292388677 182114058 898610262 649679842 126712465 282520467 73502858 886119413 809807204 264364297 822513790 449163830 114882014 245391385 392734569 454703365 730309414 516722015 801185974 932214693 171463759 324288653 12307017 267061613 385308810 41554863 65146132 332929831 436898189 815239281 272778475 855077023 433267590 428242223 965461003 22174891 330795796 617739818 806402996 182474110 45804622 189703843 447368340 191360487 999701588 842371812 869528643 685050217 669544758 503959865 602039687 872524984 491988951 52152180 642094842 983185129 968596982 962439428 214091829 198909864 798613572 189961668 911149398 227454552 10544381 473156408 948094566 863130939 172424485 881110357 630787781 27668842 634773760 794417656 674225083 805048324 73149161 709315119 906911756 557738316 372619164 17511933 514387919 266546094 210609463 809574435 925906863 501121435 265020209 406096131 178797504 915488578 538188032 381222187 252475579 506933254 803699964 935871920 789362706 175855950 404216520 360667499 881707018 960674287 924221359 774992747 852314792 491091026 323745238 92142019 141239019 607036320 101876987 813870933 891480853 58692689 446727407 639178119 125541742 483380169 830676702 773524320 359591365 334044856 956776598 640562517 136083659 439861202 659299329 650602952 665681158 37776954 307795999 813512043 13638829 67990196 613211102 340882736 607364791 173061393 26917877 160249455 297393440 448988367 10734091 659008381 796693889 20356797 216619090 15005388 208590696 827461803 141761865 563473402 631369914 981833845 969122029 191625578 350568998 182400920 568344506 442352643 733906033 26350789 737180376 460120037 990208413 971870996 369487820 399305942 793799234 252888938 373234436 925915637 8047544 681870263 254281139 793136115 133190656 42344492 118146610 749323411 268342433 475728853 237310975 292413969 231346659 52849251 748066358 63479971 617515890 628343993 624094373 348824990 125677560 263227594 213079105 911117835 314321782 981195888 730948738 643800570 43618230 928321857 115078653 702352281 831849339 997743666 613735192 9737299 691370574 514992518 208728148 852125275 204747085 644923994 741088074 356811377 909711093 570750544 762471014 759161950 969211215 346452342 685027259 501203503 192560177 338018793 249156792 954700482 203839360 413140812 15916966 785397964 490098408 885874341 647652269 986193978 530917258 700887649 958294320 116905525 372535377 582344811 987337806 570744713 893862130 759128259 956514685 739969459 776529835 680222740 402384082 920160217 132748319 296480288 86968527 735272211 375577468 952004050 495796548 833349191 579308185 812288533 41727863 667948858 482336315 521765746 272625137 554112120 346481056 183137555 404556862 220469039 289259724 69304518 351712419 600427623 58490606 505346909 551592391 574859342 295198960 858604096 77492273 221274114 434686940 976616963 728723692 191753658 24155567 574401120 209565241 357509882 235706992 758845932 516531035 979358405 800122178 560167358 966342193 53384392 60824868 202809867 858236361 564996060 105375174 273166772 232839687 524350355 183732422 809521867 731485418 245068687 723088986 814140958 812455049 122569228 439755115 953522186 7715775 834971459 468314205 385210978 728815996 376485611 812234220 128408365 572455877 336474201 926357323 345190836 309578607 734182605 218786949 658402730 734683144 268105806 189798172 611522518 780734051 572792468 649594419 432768306 129343470 50265393 760556825 917094653 84376764 151654809 927686907 199200939 297350492 183987367 53950827 817479754 387349741 619354643 472266586 341072644 885537821 210277451 572872894 742531308 898638742 993721956 43068260 382486619 665002643 69395403 841816189 876344155 450157376 722863996 981335090 548317739 208479288 49020422 139924881 90877893 415366318 126996450 935464917 843617347 758147251 160013308 486390601 561924441 870809920 675438866 396337097 351790205 150293914 868314054 758163115 87557984 944049233 413803530 301220470 940532238 738717259 317724807 866396881 200383186 441702722 987280066 555145828 270197737 100798743 144568740 774622283 805878805 964341115 395262292 318268209 839134711 14132406 587046187 414420731 188769731 534958590 3882983 662208006 500379467 87384548 981413357 188454339 691305497 858255969 122856762 153801783 247543550 639198358 451047858 946772562 213134743 949787214 459328773 279777367 764979700 840429876 436894792 457591166 521684103 106308483 296650119 372554515 250568053 553706096 31097404 602981934 898637155 361324563 956619019 840735579 729298858 176400390 649485160 279465770 287208260 370591299 284114814 461756448 478450306 122873964 940068101 685701674 67984453 933313274 113503458 196170583 278252274 37744481 436327674 459306874 93376992 226201754 338173764 466827438 557008212 636526242 27734161 393579204 934035999 682789047 692561651 626583352 93551427 889846718 831469739 574709985 492228099 173160081 447174034 48943863 555388398 222261443 271121411 756805664 691323658 471044892 217474835 729857925 533730495 544678495 979006171 671918131 782737426 908192484 442859957 910947117 3601607 886383145 443450117 927552672 504428798 63790560 321015895 733893797 540873730 619179065 852403147 588526333 107783937 587167941 389281621 661959139 297993510 86548602 917308067 6584750 534090682 950957627 259314688 126661451 30276864 551952761 346062934 705823203 881082144 248863037 761572998 331742417 451955560 705015341 956638772 657616130 577480551 198678130 81374471 30666322 468487302 52141268 43328039 338705191 978072491 67415123 847169299 281697295 322820178 847989639 984837009 620070976 612518262 350563047 943388739 555664849 829501454 523421061 745923592 937699270 748466912 228593471 924307798 578363301 229307332 540243628 867844008 659448544 905389598 887865432 449784364 853898230 424313970 946460940 168959471 933229409 416528547 97716637 493915235 554822972 914511325 600132221 339483756 605738336 611714464 539351199 350249518 471025840 486124206 116861479 990726582 594830974 149714208 47905174 797854663 228852624 142088875 630042723 279422773 449852608 537694517 820926028 853626459 358067941 175846261 175851172 172592913 773830554 93553637 567338154 565040710 392489417 371142188 206713173 188313048 640509429 2973548 222018707 987010682 72185569 677943752 773559663 69575591 875317062 652110425 67205859 649623423 160304619 369312655 126465858 724964434 956459193 880185211 3179493 132566722 118726201 426194939 601460045 262669004 360689588 261101894 147217039 494452172 670157860 750023027 734722825 218421599 44597895 890353226 720888614 38448064 985305494 277902255 445915821 143818042 774378824 674060551 957561103 28314714 380463946 440486914 599469191 707988940 546462662 262330576 809260599 791566133 651713774 809208163 189512810 280029204 873073059 87465811 476885095 889459968 880098367 873372712 615772171 89621686 8897762 56269789 905024316 837375830 973328323 335163938 170101121 614367389 849721878 100080573 538164699 420956997 210259014 593904519 399055782 417236883 606796532 138500520 108216639 131968906 941477669 132315267 217588589 599229157 470255690 799548292 258497792 974789641 583806467 364674941 971782240 652801645 141548412 160814648 498956675 281075683 673518350 648262847 662731008 430970848 459886328 944422303 426195086 215693636 256967803 191226696 134124758 46261112 466265192 142838010 445910847 81532965 230302373 730902290 810244286 257507685 84380987 458284659 286829833 828607350 345604472 939321677 466236582 626888046 228223249 425116496 724620252 18021443 775447334 803831867 965885253 724661055 894990967 933413306 321717168 832506253 928462899 812775926 256753088 84517178 381806019 997029792 306924136 659402459 608606008 115802104 328690871 26715413 326452793 516571322 673124879 200492814 669558426 416331427 942760156 896997962 844485392 201794339 471475486 159438433 701294510 594759823 514028559 384668849 831638030 197843173 834432422 927802680 240810964 452406742 458640593 327393880 733125216 246022787 513595462 260296583 609115083 21295399 904992874 529372875 509275365 858751796 614525914 289342485 18965041 954477021 54874239 676493757 516084962 175932403 723196059 788706491 941559844 109740952 895067233 631169098 26584763 512598193 525523395 579387358 816424099 787140406 302721861 625599090 316026464 24676666 151231293 506902300 361477940 250435528 28562648 66782399 566727790 371057949 232753836 537478024 192379315 506240420 414650709 914856967 623782253 981457446 189053571 974176585 202694141 592700072 296730724 681704021 441563458 652473703 822405508 788717735 917554438 517339325 776192049 738239685 426337969 444212990 129216700 141010389 953051493 240848511 828493930 440605364 983425610 306907019 477880434 262421876 412319053 739588631 738274010 31130532 726648602 566588272 338698188 807832492 333071641 371612964 98417427 503363026 389687137 460668556 872188642 938010453 17182468 461726600 268561570 359147270 154950499 490881451 779006363 905148625 196442373 959777236 366730569 250802793 884447663 376963018 727910745 385811797 707587543 165479749 60468039 106995264 139738334 883649298 836703418 858965227 7236005 660685705 730463649 24109216 139017901 11319640 276790700 910870868 852216252 646508526 251771200 344681774 739223470 270384741 140227451 107623024 940038922 659873436 147761727 548336809 803129930 871914651 510311687 968366915 53471893 748773809 138362699 638915041 863859919 444595012 995556053 835735418 12085367 936013352 400421380 684816267 360716530 898523150 531229253 888362642 614123746 66604232 786001648 873705825 267293184 489917248 405320506 247684290 156397302 433464449 481880021 723209352 784907127 502518268 953654095 280257184 66298543 464457522 263123505 561102218 979513722 57764940 682632885 602216370 437588954 695880426 374177003 847143541 998101955 156893698 429030263 211894783 771249215 193874084 860721531 806359590 447472435 362252231 484495493 191177100 599153171 19785262 664866522 817124559 660470255 558999410 409205785 809136717 570198428 827239496 922128831 927017460 342170326 429572329 23667237 454772128 110072753 755856003 148245755 291240631 628624275 361959150 148453168 782896778 66197590 24341431 239881653 854834504 178276826 91602483 501237233 175318533 226344715 645151737 735249860 240856080 28068350 479154852 844681761 256090958 172843511 985222529 560113490 501687490 461287776 430153631 78644945 137778037 359812303 770141824 218659506 147472771 987868720 584614769 577564630 825352600 482211215 728322410 679815879 913155836 621440028 955228635 247550135 800303064 888677145 204209581 272364614 875993369 918028245 916361212 781602543 233805494 681240797 572966630 991297420 443722667 966756426 501224951 16662308 598367699 92653245 782695446 132271549 45666671 427536443 21323137 461976267 508287273 999874418 153457701 807495739 477445673 391022856 530555490 991805566 640237543 224720141 458615442 19856212 1953610 756557015 682246154 289625056 210878352 974794362 131467633 193149262 214370226 460301201 674983248 120909917 963222939 358552884 131496913 946538631 935918152 769148595 178517221 533300250 492527247 769652149 452419859 407679068 150539949 525129649 90412668 800890140 276001064 997699939 940448196 167712808 923164526 892988285 509179471 19374200 462943964 317144678 94566103 880925195 279357347 926173815 935959035 338133794 260086006 888911113 367408787 368411390 690114933 991979605 668433117 553314534 280320844 996404811 98440659 873929315 59413247 921948353 189916413 803106152 34926596 583104298 641073058 142907465 62787037 857096099 951045736 540650387 111205612 112653274 395212157 578109766 127952152 566659399 522148774 75206247 234799408 857199512 8212629 639510540 357004815 522597039 56919177 627528475 481897387 437209971 53917815 481963790 964869949 535085328 513884631 399774998 864144554 494049254 617304263 735523919 115077602 843857622 279985476 72343783 913703281 230866459 410483071 754035127 918176893 560804784 782542725 181928193 789479648 429991968 116806431 641727531 732038342 593968683 568925369 952451684 16162264 451135718 542070829 908507324 410010156 880241851 924669073 880802594 15028623 329708960 417396648 871743328 372041127 769147946 760899210 831551468 849948038 238991978 213620479 705184910 536232474 173879322 4153482 110800022 855094306 880436515 407866235 18457615 476239919 152169291 291270927 799312292 869545644 541180530 19285668 595967540 952009889 631814195 184254027 217989694 834465262 772432195 366997602 98599201 550585013 845493038 127140604 483324570 950185207 911501765 207748775 256362975 69240140 422470131 68027806 46274813 848128312 636454667 555690569 770432273 960853441 25416186 841395098 732397150 662722460 660727900 750054377 337997528 882254212 523542076 608646984 520632137 156129619 845789759 978034175 540359869 296568750 30701737 96790817 954768960 803755857 351170399 357949761 637953293 451470702 91343715 599339264 682808275 26970607 188204586 982551704 52358184 566455320 448394612 204181150 239472305 274114398 938028786 341635505 473374787 981297568 261446870 66433412 812568785 337236849 619074411 501273906 518261646 804417524 860380196 525948225 116497179 464382563 341181005 680508599 720076487 709156920 547534765 107423677 202086306 639396658 28514883 568000782 689397707 742278926 468153724 382775936 45119082 327120809 123441400 714278218 317905301 853066426 386725991 172930128 262665792 539616551 728889378 960467734 41740209 467457770 420677154 465729997 394399861 828261799 148791586 145268486 147422716 472998175 368350749 505927056 993131242 864149042 518982455 59674918 67153616 80917064 244254489 708506787 999233720 721932751 830554437 816358337 830766133 294283888 157308415 642042530 739844966 759016552 630221531 316007689 216065918 158751164 797139195 226173528 207854567 592206914 608381465 632653300 391038872 238187525 889382431 87541337 363551833 143881180 705162120 399433755 296054028 677034354 138552577 54406050 740237435 183178229 964154995 75796934 857979252 246949104 973780352 945144646 105951965 334236321 408518726 394408838 569363171 229461470 192222755 905642686 507611511 83360364 964699565 819053227 799885120 889846034 543738278 77928449 456811295 435783760 390001134 624745232 234131013 108405606 487032265 140469754 607832861 793394577 724018843 372818670 820690293 375238326 643948264 402492252 174564690 231165522 400501004 843146231 677532347 343595167 876242723 645378212 865064639 751734685 816426872 871262230 218083834 360587940 275305255 619593315 975483181 224379265 854867336 767938928 986255881 110314859 217096818 511281589 353475012 308704327 760565266 915125781 507320742 997263893 162013206 776128650 120808840 557513139 523061437 815785826 867047180 441566726 235005372 151185510 178246168 862453299 490379335 659374432 302428911 572068556 80289205 942203272 597588867 385737110 174164570 415518574 184476731 703635779 707605490 785817207 420875513 738068209 650490464 517589301 585560188 918057641 749669216 722347463 659968173 41153579 54065372 599129360 220878418 688746920 504361169 825587064 366074314 688936213 712323333 844921316 597014437 719246678 181546467 881788605 394622017 773193150 356803267 678377756 877969795 312219295 287563764 985912620 840253915 401251541 579896139 213715639 307027968 817018754 844096098 747878518 316717300 70369331 683400214 172644818 301614893 118299418 841850425 715556980 908174259 490478395 809281021 549187778 283311518 538152902 822860480 167264626 476033184 751382471 724373327 906349303 132401050 944936197 485376612 420511523 665603078 809031038 968829015 199911501 210265444 590018490 356303046 6908068 740301072 358808097 333686829 613665741 371776033 494983313 28333288 131224461 729923224 156851236 556518280 58759305 25318381 401125142 544407839 449838067 125599161 837445072 662778070 674571809 53590469 169674691 758789921 512947379 846817223 732158361 781353359 899346911 922482067 126178361 740038610 393075946 346780021 822190819 370881547 803165007 818389270 838790517 223006269 305543984 640322655 770435391 594042561 882900753 25649942 102263903 67485314 661030334 281654017 979276902 982344182 959046470 833019463 562359383 263128418 537467200 320479361 189621371 358523300 885892771 671668072 934248039 557624945 149142560 231316823 276094403 197403202 91817554 222098130 272577537 220219708 63083852 38727315 418694805 818591557 257330925 183256551 697718631 561131295 387801330 433818222 536193958 52230357 324230239 838521700 907385155 431017470 221220924 751939586 924284605 103667395 842517127 202161331 271864173 702453173 131895752 898467976 754998349 560108903 121319774 689295495 864071499 326823230 240989374 609854374 208311823 290917169 605641984 703985592 434206386 614263354 839434848 568008843 198242147 597538610 647390184 634403609 582003459 660339081 163776348 192365426 400351605 380398734 380870314 307537861 783407376 159824277 225133305 919274268 801830373 183339815 96503370 963703822 248864485 235757544 718773817 345944497 943639819 580201220 324750823 910674521 148157695 381680624 747889351 395324891 308564214 345205233 893091784 771567560 411785227 940684517 275024496 151716300 668005312 323421677 431214465 265494216 675210644 711892787 76555245 624550893 29341327 577636697 824675448 707552450 326268072 389392148 112407638 978165098 595631797 705373128 159569160 820534248 312540832 413799190 116063209 364087698 323466636 796919767 368913830 424339173 67574237 553088982 135081752 390209949 741118730 217654628 790948251 487317123 808705915 278766200 482435277 790740333 966266910 76193401 928367064 705284664 456838611 184538888 764730650 7727816 356475692 899286153 698183469 762409532 66118627 291262954 551734 809380875 779167139 42766754 903663214 647329478 210009119 328086707 486950993 946191813 9225015 162557604 632673896 249610040 287691483 986600682 363136520 806176310 399996331 877478823 218206244 562576492 222244932 836422773 608057136 172418321 181114351 655674393 574551841 563143250 424425609 252241475 187451949 151430969 702464318 307846339 156076633 123689741 947774799 975628798 669991032 135293329 457048258 425226860 287121725 782916865 928240783 280348404 159332445 816607399 990667247 687877247 129215488 261997465 625127155 597309106 176532410 3106848 617322081 583483576 654591717 134024790 269067736 673528979 747632319 566431000 693079552 341701403 682694575 933100494 668098965 428400014 549827260 640435387 444910880 293984622 730789314 869982799 456163594 854285714 422919380 585263855 22983015 914167878 998809858 55117224 908876796 883760620 446105846 182693940 827825950 479525543 233109874 666416740 205656997 879787020 503735041 922759493 632985890 161987746 544031023 928913143 461131119 457147018 133874 761236088 132761095 581556195 934886508 458860841 103872118 171102938 191944874 270172628 915317025 213642770 111793230 468056578 38572810 364010360 374339725 611969390 109030089 468430221 426739532 229389053 339671347 838004502 827077328 892788365 884902685 907430 584916891 937663175 518384351 80400540 169918475 7389429 68411013 673982589 6572588 817343807 413100647 106059468 335217728 477971809 573236816 482045314 451853519 514202270 872261346
Output: 83560

Example 3:

Input: 306 1281384976 175357139 752416364 41874119 330265814 166315429 695200159 952614854 502676969 823125154 347140504 304931658 895434172 414275928 557506160 555465216 154177563 695201556 555400495 916226143 786693381 178275803 28523379 751001307 599009350 150685493 380335373 512663858 327426968 735241166 901570856 158356789 232527248 313781425 865987049 521505338 825103747 358406221 206685113 322036923 284979704 54973279 115775579 7323915 421305895 135206795 752716498 843952161 693211802 622129641 344404274 321737691 55349066 661834650 162460382 898609779 816903234 276544692 732026671 989488452 909363115 991355734 237450 404901588 160183319 773951953 211869894 431179762 645577554 846939222 849442002 8133240 175012126 330375630 125104620 63466309 973344014 259198504 828789232 804381404 493959806 528873557 741320950 138100517 695526554 301990923 754456743 270596938 181620390 834540239 582904430 748421022 218024430 706122071 126339920 352579259 474384381 900136415 255279740 611150029 465573344 970343333 658479784 294282078 810333829 9880127 378008390 880645290 358604043 752554099 876682162 870305368 96310243 240101437 60020045 420793699 760736557 193275077 388086619 635567675 837122467 938853128 331909596 814903918 956980807 947979875 565101390 990944736 213986704 745123727 148210177 101380728 5775393 904215188 302208736 59394111 835739503 203369889 433470947 828160261 658894137 289035999 167668369 773982032 657097725 147187960 647367910 282980947 347284360 607562220 738215042 126800903 613007681 754512986 931349404 497823390 235108852 190208121 797454122 21223527 845206020 225794506 514031526 628523589 679281148 248593934 424257113 609124928 419310462 641231719 180389050 841677734 982959137 578564091 253099455 465442815 293858695 72850539 257120027 83183258 120761320 36503121 702663341 460471518 205430634 545170826 847716028 831712768 385806662 40913013 507134013 695482454 913228055 70529331 606927700 448903540 84948476 535879221 917877966 909571384 871330706 587797409 29212113 242172455 502675336 279479294 473756922 558077521 655047541 725191450 538282156 145080752 49394872 566447237 220000310 439795932 920161702 120846019 31539381 609240533 343286724 515311182 7553931 100614891 733042890 993921596 278137143 729402579 268538223 930674169 882497284 738496276 800526198 602954366 535414265 691379916 862248730 446431940 150361663 634567648 952846796 921861094 439868686 7877231 897464374 820854689 972006680 391242857 109829457 972418398 65628279 309889650 696705962 641211732 592495506 613969388 390071075 166106709 682944244 389530194 532704428 706210104 555718850 177404090 410999740 269132671 98839353 383835197 573125071 806249847 990906013 629696805 562187905 221995279 152206517 687525748 974379523 192971396 120683100 424839293 258973126 349686956 910740554 401356622 47589228 355722603 867076039 815390277 769422912 88135521 904481184 477402973 90887515 773432742 961840195 718223167 931115010 491150275 510283597 832205583 623839311 502058006 475574625 495843906 92648717 304852394 448590718
Output: 34599

Constraints:

2 <= n <= 2921; 1 <= a[i],k <= 1000000000.

Loading...
Test Cases:No test cases
No test cases available.
Innkeeper's windows Reckoning - MEDIUM Coding Problem | CodeTikki