CT30125

Gino's Teal ledgers

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Deep in the ferry landing of Crosswater, Gino studies rows of ledgers entries. One clean number will settle the guild's oldest argument. Task: Print the k-th smallest element (1-based; duplicates count separately). Input format: First line: n and k. Second line: n integers. Output format: Print the k-th smallest value. Constraints: 1 <= k <= n <= 5917; -1000000 <= a[i] <= 1000000.

Example 1:

Input: 915 504 -248012 -828909 -897998 153122 962729 384090 -427320 -344243 -482557 21840 349439 181860 -641540 -704538 502814 417378 15851 -789274 244976 191326 -80821 -346354 -451090 -641195 -773489 546632 -960439 21564 -444804 -57195 -51066 88183 -353501 -478787 -790613 -486366 49649 -830539 401852 955678 126233 -337277 -964536 -423493 184378 -492306 -853350 -40335 -196730 -195765 816089 -154913 42521 -341457 419847 778283 740988 513946 442070 665862 -459314 912836 548994 -599181 -93151 139779 -709183 331179 -857808 -335221 -207521 17518 616361 -366841 -726047 -173211 613286 259554 624400 -755720 741194 -895863 -102539 39826 29262 584307 116526 309542 555661 574943 -55733 489608 678270 544148 765809 -459375 -193078 -641792 -892537 373599 946738 524766 20622 -168943 -762465 912955 -597307 -776245 -336985 -734329 462705 79747 -437696 -312100 581025 -913140 746434 6405 -81209 -711646 -593354 -100526 -909606 624605 -909519 565293 551177 -50502 897108 936489 656824 -923142 -941734 729548 -308104 201239 886879 333677 112343 -58636 -975135 -562383 -647215 460777 -815399 237367 -682535 -791367 249398 655803 -566269 511931 -925118 836820 -560912 51049 -963973 915541 864938 365739 627921 -791865 487588 -421951 94144 -920545 -761605 946070 942028 234809 -697055 30757 630594 442179 430055 234880 425915 372626 -648620 -329834 -862662 567545 571031 -460082 -851395 -263760 -808099 261840 581373 690718 346153 523371 -365706 955788 -983851 110869 345321 627192 57318 160426 977164 -582389 -86837 415640 -736994 -75752 926211 -299692 -883407 -938488 -192674 -350369 -897384 -329013 -596408 763872 -648475 274509 700523 264883 530973 -498013 224509 -480605 978674 -47444 -177111 -910874 -878231 302385 675337 -848687 -977312 733845 -158034 -924950 367556 -526397 672780 -639331 443248 491257 976898 172211 757518 704862 -639937 764437 734780 -359922 -107205 432195 48218 648821 -676310 -335926 -316883 291488 930582 -572980 -199650 313614 -461847 -171322 -600710 320333 484837 907275 228561 -875077 -308879 -601242 967029 -679139 -418214 952288 875200 87365 451608 -126680 -941186 737828 50414 14725 -204765 -288252 658116 -903351 -760647 765590 -830423 -290704 -449660 -226442 123054 -810529 368106 -283643 150087 -139917 -456355 763203 -221 65369 227760 910066 844220 -930293 253588 174505 -368304 967803 -289985 775621 147649 613535 -461892 950943 -53950 307067 254518 -279851 -977758 892330 -296197 -894842 893171 -183635 35450 215850 681602 -972493 925082 -162150 -298580 -665869 -559568 557711 164971 -63285 -42476 -234032 339797 -111649 897820 -991067 -893427 113670 -228829 949198 192835 -631236 318320 435486 -844470 101681 563249 867922 -889216 -934481 -74746 -493250 -494630 256233 -986353 -537513 809543 -624401 892889 -289867 685460 -138362 947105 -178922 508109 -242210 667632 500292 628225 254708 59972 244896 179647 264090 -320642 -962011 848857 -662164 -582422 742073 592239 -247135 229057 370353 -581054 -111103 -171307 407204 80780 -351397 613647 -679924 -95406 667594 232018 -346360 -575685 242682 255745 330500 937665 795909 591242 -503495 794656 213077 -608066 201690 453356 648309 632754 485839 647473 89030 -279366 617121 185750 549608 877739 227486 -28913 -252570 828115 782674 -244827 -809352 280026 -606954 -590390 -131525 -683735 420860 -638210 263522 544587 323243 155001 -671856 -10217 538211 3491 377180 -34071 927420 554033 -925723 17446 -199678 929251 218173 -627675 -438666 -415023 -326544 371281 -84703 685632 -137139 -731136 -453694 -889966 -571462 -110492 841653 -779368 360607 96066 370846 -100593 -293813 -128845 308053 -884456 583501 -936645 -685473 739423 -419875 34357 26925 -128235 -863147 -200295 162980 432522 518776 834273 -935031 -440165 524334 224401 -293753 169925 603345 108288 -286741 -844103 123184 -449557 836724 639362 -797465 -425429 -163434 -746002 85475 936493 -976286 -935546 -833021 305657 963294 -877258 -157355 -987556 -427059 953669 -522243 -221441 -164193 -760555 726749 580968 783298 -14629 -289133 833678 453240 -899883 868479 -904845 897204 861128 744110 -970980 171398 67452 962722 -247556 783325 192244 -581796 -870970 -31473 848054 -43679 -281876 -268043 -858607 509332 -693229 -369059 456024 365129 -27 -50794 537940 -918534 333131 -989494 85603 -617302 -996543 62750 -497443 -655442 105922 41828 906613 -829086 -473610 -500247 254022 -221628 219149 480460 514039 599806 640769 -840140 -304978 -115191 -569680 270 189991 135230 733001 581638 564898 -343998 412751 492046 -648275 237477 879727 408944 157418 -86677 731034 909238 -954415 544173 -231308 -207516 -833900 -123748 104931 357163 226884 410163 649340 509618 -156357 481449 22183 -397877 491104 -832206 434212 -876588 -294103 136273 28685 688168 -428853 -676071 -713251 864759 -968364 -343399 -591126 98349 531273 345795 775408 -244463 320571 491113 419104 -946330 966714 403720 -226628 766187 -416083 -743030 -574436 806923 453947 808286 3164 -41778 -830263 530189 748908 -417204 570127 23956 564076 637857 771342 639425 -844713 -373968 991592 -496166 311198 444806 -532991 -387696 587515 -659089 250335 610463 636489 -313587 514714 -392677 690842 528847 433912 674585 706417 841184 849794 -467250 -247079 -100469 786487 244447 -535506 -899190 691616 512037 501665 -899846 26443 727064 -534729 -94032 638810 952881 -374396 -5504 -274544 -228955 -548236 184076 -68132 553213 -691076 444031 -400440 45461 -787624 -127657 386190 -816556 -827222 -10603 609143 350232 -672548 290682 254984 -358735 -266400 -802853 -551531 -211778 745280 -113450 809931 -322774 -379873 565855 -908769 953398 860200 -997757 726041 344936 447587 -743231 -288969 -584127 -171910 -17703 -231012 904308 835035 577033 -419217 -512357 -762557 -33091 258030 953375 66809 107577 -269652 676475 -153222 -706903 505001 804026 -169146 -75458 736164 -529137 153879 -376824 485187 -403675 -59696 426850 89230 -501441 -31106 -549513 338062 995 402463 209278 737111 -487632 987059 -784173 -467118 -613384 -835764 -882054 -741961 -844324 -286493 -300227 -624563 852669 724849 -66682 -462810 499394 321026 420058 162348 78970 25407 -371426 755063 945624 607696 -597558 350136 -703107 -439669 -508848 -557437 -404405 912199 -999857 409116 937457 -991373 277601 502987 118551 -115908 530936 644747 686154 396393 -564916 -380577 -95710 -193982 -539569 179073 -213396 623378 271448 -106288 -635413 -1109 893733 -918135 556190 -766630 806919 -787633 185679 889357 881472 -989919 -745641 -744677 771636 -968450 560392 625687 -883092 -48993 -7881 765047 -924022 -807586 -974371 -37719 305115 -644702 -348212 -818861 608178 -776454 394006 -226932 117655 845731 -310764 763501 -242874 938859 -857151 714278 408994 647822 -911448 106181 224802 800116 74938 671307 -882433 131624 -252240 181201 -428200 20116 561481 617732 -189853 -370259 357118 -590925 112313 -806586
Output: 116526

Example 2:

Input: 2856 2772 917028 -706236 -536949 96083 -37785 148475 -620521 -418582 29251 639992 925955 498521 -674085 -68846 905332 929538 183600 -281016 -82869 -835348 -399785 245060 379102 -348088 -840366 -250372 368336 648625 212782 398351 418199 586069 -512646 -558248 -291567 -436325 -409373 -322283 -334968 -150609 -194006 412136 729904 -120061 -254672 -973153 -365452 -937598 -935686 -757801 -249078 -935122 210042 58591 -907048 -825374 -80073 -557010 -291100 -359063 -182138 940375 -300341 5784 969829 -817307 -986991 673782 -892984 777765 -150811 417710 522188 3045 58888 -949626 905333 -485374 452739 994306 -687300 -835730 -264048 90560 -378107 -944720 139623 274308 214787 756305 -794217 -80631 704838 -937002 578591 276865 426613 111716 -713566 769441 -460272 -903388 467103 636266 171101 -773225 760587 626497 851976 -855335 166291 122584 -292716 -333416 503224 -513781 -989210 168634 363501 -535993 274611 -189754 -503107 867532 288772 -499923 297358 -451025 -613039 371269 601464 616709 89027 8212 -197297 709072 53034 -377219 755412 915719 -571519 668230 507151 -326805 -939824 800779 -227137 509416 -6497 -938306 -414595 -874098 272325 268703 -463681 398177 907448 905018 -518469 -443496 -31582 -742511 629517 -627557 -733741 -990015 -159466 142849 -357553 -295019 -947926 -378077 819585 -724996 -911540 -35607 77141 -935816 -294453 -258828 697754 949806 482080 150715 416111 -426207 764715 445311 -504896 -620628 -63780 -904286 287740 -262084 62564 943378 559199 377717 -984660 576417 -352439 39867 -557059 -224456 -693314 -484901 -52234 981087 931188 -260969 -450493 -106337 627781 650645 583218 86267 -628920 833829 562267 496819 -521742 -661782 510876 259555 141097 480604 532157 -380014 -565883 -99290 -398142 -881165 102037 -89619 375258 436025 -968119 601089 -390922 814163 204940 -228571 760570 888336 128700 -927592 -977809 -967256 -768067 -473065 314236 -671827 -602156 -859582 442466 -620929 600595 462476 727934 -482099 285998 681588 -432644 -793326 -626068 -701387 -555924 746728 798871 -794397 -419397 -180506 465365 -729596 -799866 287152 162178 254911 -766938 -458017 6332 567005 642702 -786556 989855 -386750 -551233 -161880 -940204 559524 -176037 62816 -798927 -232405 -98444 -1316 398471 -244216 67396 914919 88561 577556 -436822 561857 -955137 -311595 -43837 -137340 796741 -597291 389096 86745 45870 -323441 263576 -946413 23959 -38290 -66236 351475 993420 360560 -623638 -899565 808498 -184748 469098 -736075 -605575 -926863 -966552 -419453 751953 573264 -37643 523513 894111 -450330 -715389 -45655 821575 666314 386822 808900 -30772 -263927 497745 82751 -833742 -49805 -341694 877587 -985333 -715288 572185 -130079 226362 590403 -156959 386467 -798924 937278 28237 -666359 -274525 -158073 -803474 823589 -165485 -178312 909946 -767427 -262298 -165233 49957 951867 214583 -306611 -363139 -598999 -301982 -193601 -842600 525989 576915 -384479 -867857 -909758 -719542 635785 869641 -219797 -510397 2287 -194996 984621 941963 297966 681393 89366 310463 500588 558285 536948 65955 596929 -910122 980285 344772 673544 394377 259752 613038 -611145 599599 310959 298206 310083 236451 -323811 -694966 178710 -939594 3843 989758 -512700 -835357 -711025 -228348 -330098 -223226 -739567 245928 -861957 -284159 -64504 275398 -355514 578634 459984 665824 -783717 71398 923908 120814 -520604 -225177 -601845 -78318 -102388 -734455 167154 -515 749909 612101 928708 364074 -214206 173871 -23752 -401193 264930 219491 605332 -497697 -592563 814453 583976 -906534 160980 29245 -587041 -801291 -166967 438961 687816 -119970 963891 -956794 -50624 -668134 -293454 -713688 480564 672630 -251962 -852172 -28480 -82450 -728313 -318781 -525585 260679 -943330 -959071 -84726 -451522 364855 910455 -983094 122780 176174 -678294 -421291 440678 -651878 635433 140392 -450409 984168 702170 404942 599527 -639866 975189 559875 -38298 -658485 -136453 -966562 882945 583947 253195 -75562 644089 -460562 -246605 513784 -123969 955581 -519856 -418141 459732 129650 -556659 445556 -511713 451559 586747 -857752 -301912 106890 640992 -260362 -308520 728501 373660 -319724 268140 404433 119257 530428 469368 160245 826921 -423328 667104 448627 -443008 -198203 132780 -315628 587687 -652859 881504 -125054 -678140 224150 788703 -304614 -941415 711525 -770896 276589 515465 954433 -863465 318450 -387447 941312 -231100 718793 -582617 -54549 447490 -453071 -710402 -407043 521313 5043 -334151 -398200 -765507 -952263 135059 84150 -982486 -474314 84802 447571 -348770 -299285 47951 -718033 599632 775561 165212 660804 -518228 -233654 532394 357381 394880 -119824 804819 -469127 -614331 135824 862653 -930802 -476595 -631483 574810 133756 806808 -684466 610579 618355 113415 -952674 103021 -639302 386129 -986178 -541570 484901 829992 982783 -823948 976971 -559453 390657 141920 229791 13838 -949912 -152557 456032 -914635 -925176 -394445 -838693 -594584 -678546 -173008 -34153 804202 -420674 -460354 651104 -502798 -600844 -767697 -870399 302066 815942 14158 81134 -113150 941017 -488924 257057 -880343 385034 -131426 67285 -813676 190531 -903701 -827235 -452631 879331 -245915 899163 836140 645493 606315 298913 -346364 -769632 -155051 787395 649868 -270812 -859799 283614 -201163 -489158 589049 918105 -30884 -698148 -367802 28947 -336310 -605783 -702497 -867861 107655 90331 666986 348854 -858376 -414769 63715 780675 204093 371818 751257 -720011 315311 702646 251710 -307582 123249 -997364 -842979 -806142 -106502 639713 763486 975160 -799433 -22671 476349 -774690 -944820 -702888 -466757 310682 -684618 668211 -438140 -63400 -937678 -501991 -695998 -406544 568303 -697394 168024 -111179 229140 -464635 -577250 739391 757515 -2286 -950730 -271642 -91138 850631 -694719 813076 -48630 749458 -830444 -314569 739933 -51162 -40985 -991301 239362 641576 -322464 -83809 -67463 -567953 -202274 -581456 -264126 -702042 -257592 -39630 -442017 -240979 525693 -630051 341959 -104690 -221900 -707941 -578909 -876351 -563491 213629 -519772 -396790 260818 -864501 -484081 563634 911279 -811003 -294540 -337519 -938441 -770393 965138 -707095 -666870 435752 210784 524771 -957163 -23468 -840642 -28441 808602 440438 275638 392773 -339539 64767 -20370 -203832 334069 146001 -264189 -231068 -889896 473794 -621937 479891 524744 -668804 181350 -806101 10395 -342277 159135 619389 685674 -13371 -952021 775994 930680 -330208 884094 -347572 -806482 -429081 873514 -768500 -726743 51623 -937667 575391 943819 521300 869719 -382983 671779 -181106 -613371 352491 -869846 -528622 -215621 701581 -556135 170097 231075 -680187 -606306 -305536 427248 -411991 752782 275824 589638 102212 518430 92056 655136 -269892 -548672 -155982 210405 817056 370159 582192 101208 503706 -391335 -673122 152802 914285 230142 897614 409067 -813585 -822778 -443437 951238 890629 -59188 728526 539954 -51917 183629 415963 -132058 985097 721343 423432 -423666 720721 -31144 -955558 -815910 571397 679310 -715033 348621 -46756 124081 -790050 -903525 713778 131066 528207 950869 162639 -468614 526015 -604882 -64561 845676 797084 -191913 247045 975190 494224 697770 498091 71745 233635 -929192 628056 -247166 -102032 75004 587012 -363644 -198948 -874054 -837727 313431 -84343 -600188 144849 190711 188938 616540 -982853 679646 -21248 -438437 349823 -661772 -846717 952295 -611002 -627380 527344 378176 -366115 -185413 844839 -677072 84779 -85746 -716131 -7715 398552 -415500 745882 -210507 -529400 -908103 -334405 -503926 -431664 -521080 910032 -386911 61540 838756 925360 438630 877092 468098 -833835 112445 -805297 -118774 -838889 488454 -532220 839138 82973 -104897 836996 -634413 628037 835215 -908559 -1572 298241 812472 -842930 140290 67914 -354613 -458618 56479 -37843 -511910 365210 -984477 537768 227750 -706210 674255 -355093 -12253 947358 556260 -185716 854738 -801956 -510610 957511 -822479 714080 -633901 235271 471330 734720 -829217 -392220 -415608 -136447 318304 981491 241446 252129 -272232 -340721 54761 -979798 -443890 996180 -387291 283673 427399 -213758 242557 272126 679897 470292 -66579 -39179 905632 -108208 -381356 -587011 -949848 402716 -519793 391478 900270 937827 -218905 451000 206174 438546 -386806 -838297 -923375 -755443 738174 -280007 -334474 947149 -554127 -475298 459208 388198 -209788 -677845 -348364 181462 799367 -404625 -783137 -914698 957958 255147 460780 -783406 -505549 -764801 -545068 127750 -851578 -680784 737099 498243 -760082 -108495 361930 182200 -663137 234879 -43404 -844286 -367440 -114434 -610398 -579615 410512 411501 650936 -50073 -585426 860603 -112874 -800401 -450719 -374269 766380 -100852 -501224 287095 32866 478658 726876 485613 -56826 591271 -646069 407267 229731 157704 -418463 -292006 103562 -120640 -715755 -166269 -891651 807495 -512310 554397 -819227 -898093 -656463 748293 -619226 760247 172062 -8480 345696 -247812 -775427 173829 303147 582686 301273 308323 -284620 -296978 943770 -237932 343825 -144210 -554349 731533 -317164 -413305 66723 -437039 825755 -687541 -534432 -453906 792474 -171329 -868858 -747526 731270 -343111 -153370 -348848 310941 -676582 -996901 301723 828769 -725438 780687 12421 -765127 -142421 495678 -414994 -31327 39371 -808797 438605 -512544 -599543 -614641 518853 902253 226948 430317 603858 508677 -739781 892333 -405641 -613353 -811216 601753 -687309 -963942 -520007 194451 302321 -169377 -428157 -975081 -763388 -689768 791534 -51119 -888675 -924605 -58873 -764919 -634272 707872 -987147 -329428 955845 -904417 697295 -637988 381446 -823212 185613 30903 -875085 793798 -563737 -40830 -891009 582121 716066 -129478 -158771 -562922 858542 -983137 249627 618358 -694291 464467 774679 -649527 -679107 -961417 678053 -596520 -192775 811556 860703 175612 597881 431895 -803430 500290 -155629 587164 875293 -177932 768391 -257369 558197 85241 -801600 539399 -214223 -542302 534971 -648097 -535421 -427674 -458491 840337 846523 375393 -79617 -663788 -214668 -788811 -8592 -196983 -986442 -691193 -397768 694869 -473286 120841 -294725 12431 137475 282777 -256266 -939492 576244 -506895 892170 788326 -784856 -214045 -49440 -307880 -414205 283569 5494 787189 -546169 -977374 -612282 830862 -487279 550813 616754 -838744 989641 -736355 725622 182560 291693 -873764 928346 -603590 750307 9811 -515582 135525 57017 -374082 100095 -483850 -950328 -785446 -498500 -734914 612342 -585396 858851 -483270 -237411 -605709 491644 69876 278590 161581 226019 -494659 765706 -315351 -708685 147329 50992 383112 -946854 -871554 -565034 865077 -962803 556180 933769 -679190 -471475 -708487 -556918 483165 568283 -194262 763286 868494 324708 -297173 -880495 485958 -429658 -525189 -723925 849970 904000 31483 -824740 -623534 488452 830283 727328 -717097 664037 130266 -564605 823010 407400 185887 498060 937601 537065 569073 726940 -424950 -643864 15730 -872130 367492 -400120 -231735 -591283 277789 695425 120325 47691 -886176 -869419 446316 247611 586776 -890632 806287 616571 969858 136930 828409 -154420 891703 -474286 -707698 287133 496726 675555 969518 -759987 -667954 572773 439734 -62682 -38780 377425 327933 241651 -127891 701244 821894 -490319 -517352 -4686 -943957 803876 -976233 62563 828085 -302873 237070 663581 890013 -782992 691547 734 -535950 -634319 -747619 797024 866122 334614 644433 659821 -20179 24845 -691836 827381 -81296 -113054 642798 827350 601678 875048 688866 704675 -697573 -431432 -2465 523126 634694 828372 -689425 978374 -646301 -38507 880394 720947 149989 -57282 -40126 531012 -474507 -516433 -461834 -767614 -828992 -675174 -782725 34482 908936 853499 708767 -707211 -684758 -686813 -292067 213277 1044 137708 471876 -396690 315934 953402 -501153 -834263 -246224 -253756 -25023 397401 905985 403391 -983497 -699400 410031 -2182 -744555 -416467 -818978 146736 322176 532491 -977433 667532 -985271 -787456 680275 -364566 -686792 -74643 -973961 128105 -250687 -647578 -713935 652826 -244810 731426 391559 -972017 -932319 714338 -2896 -187724 -793639 -962892 932817 13541 42050 -793635 -735290 900100 -700619 -446443 -128452 699459 -78975 218076 905475 430354 -129866 -447062 630234 -350984 -227954 126031 -148009 376557 901906 945489 -218964 839370 -432592 486219 -929010 504957 838791 -384348 283070 -700416 -549268 -765746 833151 432986 427862 480266 -506993 -814765 791028 -492453 -948206 -338127 -521064 951030 861840 -878328 -621380 953962 -725258 -978095 -21701 231743 672648 -223330 -947843 -909082 -389065 -303458 103010 -707741 435673 318681 24652 285647 382211 -170658 373554 488049 -839131 86698 -753983 -356454 625010 -171513 -325626 -861923 810578 -21920 478259 -764912 -796389 -42668 -931753 -170275 -279729 -565738 -532590 -412321 -780313 -956760 -939825 -103709 -804893 823966 -373663 195417 -667627 457996 -752913 845192 -78592 -530526 -119083 648587 -705287 -429060 -217557 239302 77102 69887 74671 -781061 794928 348256 -500536 215372 245190 -987433 -393007 294864 394001 -654427 753817 -264828 -539901 -326862 -418645 -141100 -532850 -240124 -207085 400467 560008 -783860 641506 561578 -85488 -549625 392638 -225938 126661 -598877 260372 -883698 -19164 -182828 319477 19095 741646 -93681 -398636 57466 384817 140520 974237 -428698 -5868 455056 -789123 418990 412219 488803 659347 -103414 -630955 806554 -286379 316460 712603 580905 -339899 -836509 691802 860126 -147549 -216932 381625 -833567 99616 217264 -657104 949030 394428 337098 645388 725789 372212 -940255 -388179 -137785 -393779 860366 496056 485140 -165135 722157 -335549 -493163 -293532 312708 -209485 -962064 282565 630179 831524 -244237 965375 326402 -570409 -37476 -119689 796841 70239 417228 -848029 830800 -949203 67331 23118 976214 -718138 671422 525847 616316 -295143 717804 8411 982780 -360069 -974246 688896 -959600 -553225 642801 -472475 -182138 -982173 891534 758150 893670 621751 309914 238346 -403603 178604 -317897 -356526 -386065 -961682 634622 -565067 -102053 945534 971766 69557 -163805 156133 681851 561463 -834661 -636902 -171105 -524956 -496166 -304793 196778 986207 -88551 617934 -366663 329130 610793 -164626 -714678 -295356 966925 -484353 -632796 788764 499637 993017 923017 168599 433314 -562008 488652 785994 339989 -176871 505612 990569 516649 -326251 505702 953075 452744 392438 -737485 -501526 -249607 597553 -793387 781010 -555175 857521 46673 885429 -25850 479174 203542 763220 -985059 65503 549822 -351351 425122 -447026 -993894 -357956 498481 119907 964008 189076 -219298 -75308 -613455 -314076 -62490 882618 663639 -51715 -545533 196123 -947875 380148 -479643 -83502 609559 519582 -20082 -481417 -936215 983884 -51624 -295971 -959301 390175 419626 908254 -140981 -982452 502167 -694600 772863 831364 495184 -913584 64344 -437188 13426 914741 833305 -341554 -865812 -996647 -67599 -531083 -980485 86881 -994687 796138 374397 -40940 317612 -196262 981976 -404363 -714106 78744 704653 614862 -570335 -41519 -197432 -444073 -899259 915739 207349 500660 -931040 391049 893052 -174037 -238757 423459 -722026 -379134 285161 514250 468554 -771001 758102 405817 -765230 -10670 427037 20325 702579 -571066 -225629 -929101 -50166 924994 -641232 -146841 -418992 977015 -860892 -829345 84539 178089 564993 -947033 339524 -137212 -459927 828339 -670761 -565255 -230333 -401469 920348 -853185 -599003 939120 191746 -686876 -566742 13436 781360 10989 -706719 706433 -419047 -958277 -405583 -904128 -122214 -677660 -558048 -275698 53855 -303210 -5730 -931981 419937 459070 -341414 80494 196657 -921207 239116 224144 -434928 -385145 239434 -805485 -927737 -806686 -178018 -957459 -988427 252205 -139858 -174253 -305847 936399 -256283 5238 -355628 997809 600229 623568 -91557 -972441 -635181 -30928 -818191 330060 -896619 285795 363881 -384794 -143775 -53301 941111 -253943 -432500 923483 516802 151299 -432526 -392956 -258646 344262 -207422 -8021 -386208 881523 427593 310805 -334471 525973 61282 948693 278208 963762 707233 935629 -766563 176293 346070 -773168 923640 501968 -732540 -552077 508510 595691 777593 -690986 -295654 277820 536049 936867 -368146 -379059 457107 653896 11124 -496579 -525908 925189 635648 -374240 312397 -365134 501108 -837181 275986 201739 -95239 -283253 237906 113822 828596 330829 148412 987508 835069 -770355 -570482 -866645 151181 82845 -162213 -313748 703687 -813217 -480974 -884486 915193 -712591 -774668 931290 435992 -578330 487694 290094 -111365 -428751 -318702 -528016 113449 846922 -160673 169538 757689 -419745 -649154 -444904 402593 -415523 -570554 687909 55431 -820459 759418 -268448 73490 413353 692337 -428224 816781 428995 27141 547803 -277917 558468 -610564 235877 532027 -23872 988600 770863 -251744 646936 -881285 437055 -986207 -304382 -636170 110569 -155766 -728493 670613 629781 323034 383881 -167140 -351386 491932 -822849 676526 -723803 -167877 778372 -357529 316705 394800 808466 659136 -596000 543021 672191 -135635 520384 -903548 -552558 12104 353390 -262292 182709 -598152 -369851 -371859 -661473 -67929 285562 615880 317384 -558665 -850343 -113277 765789 54553 179415 -749643 642428 -57442 718715 -846021 925096 597389 79600 -308080 -683189 827498 826181 -701609 -546997 342248 991179 898695 854707 -955296 41405 -99271 756408 300676 -639533 -578176 -545240 74901 -440150 -98730 -3914 -361336 -159054 -991680 -77348 -52433 -579310 679716 722457 974126 680365 -62087 977315 752888 -941929 146580 454489 -86632 -819212 -365689 -689646 -542976 -774533 601639 938171 -888128 739284 -391881 -829567 864243 -292786 769803 -571710 -154968 169322 -820754 661450 278441 -60246 443993 145445 735661 804076 717510 520007 708012 375704 -646158 -709685 -842349 371572 856413 -971424 -696066 -562701 -433018 981316 960915 25369 -603997 517870 936022 -219146 92934 -607850 341445 -944309 -836314 721709 -767923 -27486 -386406 -289751 -5868 -276566 183450 956481 641222 28319 -206664 -692369 461245 -252509 -151952 -651937 512211 -116746 173763 -105222 244937 -594989 51750 -520174 80 969320 -637884 14866 780874 996805 25972 769895 621496 296991 13494 -402042 778804 877947 -789008 759759 341774 999123 512625 474515 645905 356010 -775371 527566 -810797 505789 -97655 320020 301985 251447 -132336 338169 -126963 -473670 -256500 -200799 -27420 -987972 -946444 -488965 -125048 480658 745885 -270518 -276933 -211218 792464 -825594 201283 -983364 -641637 -44245 9234 557840 -20600 -745888 740823 -263099 -670171 917212 601122 -970380 -205109 -854595 396076 -716523 -16365 549066 661098 195279 252105 -955132 -503212 -623156 -201879 -832053 959029 -177473 643038 -41704 -551482 810138 -660707 253615 935501 643999 105677 458546 836983 -865666 505883 -800387 976953 -415249 995726 -89770 881677 -283022 -116432 -564837 844938 696209 101817 546291 375678 -409145 -156845 -58045 649364 -537199 658276 541672 463319 765649 -514419 259289 915020 60844 -490876 244252 640011 -641711 -844224 -454437 96110 -624678 875114 642257 14812 -243381 208138 122187 -571247 -181035 567841 961491 -421607 -491239 278825 330817 195056 907178 611554 -214393 -611905 -939746 280536 -352244 934083 -742284 116985 343530 763181 158524 -540884 71074 -761185 -104508 -495108 162784 -977176 -179485 -340511 -167284 88607 208051 278626 703548 -620653 -36035 -106098 728904 -826266 673031 138021 253036 -864270 -874114 959162 391536 448376 -403070 -497181 -674906 -95101 687823 129935 565211 -995892 -354995 177522 -416072 880999 555461 179329 401835 -955407 -138827 -991569 -127566 525566 730923 -392310 -809455 -256485 -201826 -795134 -529174 922142 574694 -288828 529957 -155519 323155 813829 -712583 -170536 671798 449428 981918 -100132 556261 -472696 -628634 -125455 -407536 872591 -417548 -549184 -951640 -149180 62121 -768800 -807794 -961662 -310233 860300 -334704 101470 -851138 -195782 -173316 171444 492970 929694 115680 484130 967986 -760601 802327 -268060 539954 -836947 -687004 -337752 110671 -383154 988292 -174810 -324972 321088 467982 826395 712338 -720498 837579 596062 -280763 -731293 -484107 948943 386854 -693551 -785675 898713 -483095 349222 381977 -877398 104182 -779874 520414 -658755 -800376 -759503 119167 -28902 964789 449246 896026 -637138 -680905 -720213 -592970 550512 -541205 -703083 714986 860979 -58904 -754944 -189332 -553756 -859415 -163200 912299 521479 -674652 102555 404577 875981 120177 -55405 887079 -60477 -805164 -893603 -305830 -481980 -975133 162172 -975668 -638381 -467065 211874 -224074 752742 541548 -242224 79107 -554986 802742 -994715 -816653 744495 362029 -62109 953395 -140664 -725424 334284 -123001 -952240 626340 -344577 65626 -467400 -709356 -429833 768699 -133249 647850 -165668 -687858 967705 215439 -329456 -428750 376660 433269 692277 -449629 105132 -138974 214716 -842057 227886 -758056 739577 129595 203778 -803556 320744 403497 -8900 203741 609162 -712026 286869 -335952 -912260 969497 706093 932569 -973306 -405028 -976225 -46640 -539525 449230 -956774 -693556 459237 315259 718869 -830574 208328 -702632 223557 374487 152955 -25432 -2972 -229014 -981240 882841 31189 -421143 179919 131733 -955352 -271377 -401751 268349 350382 485414 -498991 160977 -380279 969017 -490519 614837 -889944 49164 -129774 223937 -729261 -594299 -975789 239488 -96678 633768 -985715 -201706 -184786 401737 -377510 -907013 533649 170642 149013 -334602 -476887 -666149 307858 5307 628656 142525 713648 731173 20994 314073 -272796 -128722 -546343 -157251 757341 566887 241835 936134 388775 -996573 118315 863699 107660 -445455 -422062 689481 138270 123544 363833
Output: 943770

Example 3:

Input: 3149 874 508799 899598 89218 -787822 506194 481502 477919 -37661 362715 -582927 -662394 -297565 -358150 -322821 -843666 -643963 535251 367707 703203 -165180 -859564 316059 377483 310446 563083 590798 -866733 -187176 -158849 -284475 -357185 -113118 -160493 -412681 897831 -534379 505299 -266305 -490488 -564982 399580 219765 -179794 111149 -935586 -295107 856301 194683 605123 -186679 508865 -434185 -310200 -167116 -445940 143797 820676 573607 -568574 604661 337153 -913042 -557393 -580628 -826073 -551226 338064 -326747 -376027 -812856 83840 -168864 168042 505015 -316370 32295 -993320 -392214 141352 -826057 -339821 -511099 979417 864291 394597 -468436 -7330 -296186 -833132 200023 -888651 -860571 583400 107909 -702172 -556661 762306 903198 107526 -427296 -814155 -363847 259699 238151 -863458 885734 790261 783115 496192 -128919 -858141 382633 496759 955851 649069 -278041 -514063 901579 136027 -948858 -523756 138105 616481 -684641 628075 871139 -393653 187754 -992043 132657 -138650 -558747 -989330 -103323 -411889 -938790 -418738 403766 -199505 -162347 -554590 521770 -373153 -20321 56937 294899 -784671 -777850 743790 -894555 -236429 967415 -424245 263575 23691 -406289 -131096 546475 -348742 586529 -240721 186796 203637 -767207 645498 492271 -669736 18811 -792293 148291 785590 611412 893284 157478 -733473 -862802 464666 923722 -995186 -805924 174745 626610 479352 -744469 745490 -177984 956144 -44857 493264 -289259 -856857 -947647 -488129 -59560 713989 -874755 964730 392805 494375 -959714 308765 -309126 410558 2834 779578 -261248 -963276 31280 513603 937124 614707 -668817 -195764 57117 -242322 -466460 546849 779558 257171 162772 504153 -815657 -359642 119692 45429 106958 -630471 -938443 -138077 -885609 -615011 100962 275195 -735506 979292 -169629 832838 847543 588592 -527145 -178509 258515 13061 870558 -215831 512329 910379 187594 649655 -138068 347961 424853 181857 -79838 733852 117406 -647764 552254 -251180 -126900 403848 -367315 -770081 -654802 -165172 -910771 255677 -909935 978000 -357818 744113 -401807 -676377 653153 -693645 -714597 -540885 619003 468918 -140746 440348 915026 198145 -431877 7281 -160347 -489545 -550995 410596 -685226 410171 -175514 15448 498441 357873 -776834 959390 -216510 565742 -45487 -870430 -679265 -736063 -718783 -649079 -576101 -317095 -196698 -204224 791083 21077 726617 527558 939418 714921 772388 786199 934209 -514850 -23580 -557518 583678 -328521 -285533 776215 738399 522195 471097 891856 709474 987696 -631764 -621720 -726080 171980 306408 426925 -528721 -30234 642639 94680 -852343 -558007 535954 -352751 205264 -31240 411892 -431297 922776 673082 171532 -410952 -521720 -705849 439449 -274371 -368139 937663 726446 -101028 24165 10239 -588290 -271022 835294 895847 318073 527503 425399 199750 -894170 335184 638664 -519146 -803969 -399044 -626055 714743 -647359 373817 945547 987808 -220329 995583 -533107 -90849 521755 967507 930263 351012 -376921 -725274 777541 365223 -956413 698533 224564 -384367 333711 -429376 668919 622214 -393644 -914726 767985 146816 -585899 939338 499599 -908524 -156451 419579 360690 -474817 518392 243441 -390712 135068 211314 648183 847337 -337470 406938 784219 -35226 877385 308531 221399 943405 -59667 -348419 -569806 719065 -481259 -766157 76529 -828117 -736115 336361 308209 86734 540600 911905 488883 -769581 770497 898711 608990 -555640 995335 -162234 449438 7822 238706 -749009 -895144 -992555 231020 -881286 -986738 -63564 549944 191684 -50281 534746 -869295 -317081 620909 179662 -808221 382975 -673029 -430284 -952748 78700 -258954 -444457 -430093 -35247 845968 901323 763855 488604 189649 -298642 -257933 164320 856888 -30502 -219360 47225 -363924 -185829 -610678 230770 481418 963964 479150 291063 -571661 -573651 427367 -226059 -953926 -20999 819410 -382233 -100322 87528 -153837 294472 -718617 -937215 911473 -417440 -387685 745175 305156 386067 -880146 -195323 -720412 -321713 79187 -267797 -907792 92796 874695 -999894 -595107 -977320 -105073 -533649 -723490 625111 -513780 746641 796246 -294620 -996744 -857551 312758 64834 -947972 -675533 -256395 662064 -350675 441958 749736 802177 406903 775063 886167 -837527 726734 605776 -680191 138138 -569165 705488 468046 483090 97094 -252902 -129347 5605 667586 -510365 809648 -403458 921114 -614352 541996 966625 -199621 -142781 851373 842127 27291 985747 523851 -620373 -891473 -195915 230169 -178481 -506562 -659306 -686339 589911 -944445 77511 854923 16534 767803 -223227 -707904 -121467 871779 -756687 20258 103565 -415492 712498 37134 340544 -678333 45372 446690 58478 663622 767538 -508589 -713367 598637 359440 -55340 188441 -711621 -245243 167108 -117677 104136 642059 398519 823803 -573284 904161 206071 667804 270392 139346 778506 346267 -876024 -97218 161070 959510 -256878 563189 -584581 -527023 310613 635092 -490190 788159 37913 335193 -333090 -856458 -720326 -588696 -615575 -713004 866910 431283 -518753 95224 -766534 915803 141981 232503 627478 -162116 653108 -98642 314703 733586 648878 752673 932377 -807730 198902 967536 -825542 -118182 -772988 572213 705127 -866224 233131 501019 -414784 932753 884312 11962 402497 -553730 -595734 296759 -764043 -569058 -575152 -154476 -319200 720207 599756 -390375 196090 669374 -504245 -705252 407862 614376 837746 969829 815949 -893009 581309 625765 -614588 -806399 744081 593101 373900 936905 -666503 -809833 103161 679646 406720 521033 45119 193016 325356 -989476 -431156 216843 598130 -871714 -167004 -840220 -2176 880964 294404 646919 -697930 -976218 -995834 112781 -462452 -444119 79477 547235 -416498 874104 913353 -334569 214470 -257279 566584 912678 -661852 326673 -943071 786596 -466325 -421225 237145 176718 176195 922363 7355 668512 997033 -832529 -318283 77059 -395177 58488 804013 153435 -232124 392885 -712461 588140 913529 637473 99082 232230 286725 672750 -817979 91528 829212 -807600 428330 -232756 905341 -323843 500950 409542 -511487 -424689 582869 32705 138471 -353719 844815 -746120 -509245 -692055 -500493 797739 10447 434524 -476447 550910 -649117 925638 258087 486871 477436 -221695 -506356 -509630 -353996 -152291 -495520 865357 -183731 -842834 435509 501754 -168000 795934 -543669 -955457 728136 -505363 -374119 574727 88928 939756 -649467 -372577 771142 -536108 874875 589016 -666391 -837216 613313 6108 -747812 -819767 787171 57766 -527046 517692 874953 -823322 268208 -568678 -465261 268688 859618 -361185 -91150 -453677 989314 -477103 -20712 -787503 -360065 -613186 -762334 320720 298087 -83433 841684 -902726 112347 577056 166952 -401514 -738086 -554633 -7481 461195 395085 324381 -19705 -701113 -626635 367943 -449566 518053 -850970 -720928 583913 977028 -208866 461839 -149592 -486425 602673 279035 -571125 -855632 -939122 603907 -696203 -586409 893193 -474975 243972 676405 -729195 577039 291043 589373 469619 -640735 316376 -652701 618965 -495181 978659 719317 -206532 -236700 315848 205118 487496 -818216 847334 386486 850920 -685166 399301 416474 682144 63218 931320 -956199 286287 -747364 -225398 -954351 338564 -797758 414348 -179664 833188 -572230 332174 650100 -25127 -873452 -482063 513391 -372765 971703 -585143 806989 -762415 440969 941715 -489429 -511977 894347 612054 -349052 -127020 879652 77646 335133 286159 -670413 -810083 872868 937787 -680992 -755309 -683021 -821856 -63590 -69193 -807628 -101553 148140 559231 -389997 -544562 342694 -2816 297010 454544 -275169 -396058 121870 286812 623820 -625372 -246628 -57311 -984618 -825178 309067 807256 -870075 881797 -939219 -393183 693734 -34593 -115674 466701 268834 886538 -134436 -762076 -496400 820769 -326275 -455101 898554 858421 -204413 365357 797433 954604 277167 827547 -209967 -372543 -956508 831781 -895463 535349 -459067 600105 133231 -838778 803482 -319901 -903697 -77352 63756 -789657 -553119 -796511 -150249 -407362 114906 343071 -946838 -623975 -474210 99188 -932163 889663 -703904 -751825 -86180 -414992 -861217 715370 563648 875164 472365 -556968 715028 -676567 -790203 749852 794745 -894868 -98223 350386 871764 -952402 -468167 299963 -217233 693422 419270 -969221 -332239 573051 178046 520842 411368 94119 583658 471514 584988 -112907 -723123 640205 889738 80626 491871 845843 137000 156846 329375 708180 -778772 11249 724767 -171424 -219405 126123 897940 354088 -443677 -213778 825045 442517 657420 975025 -442473 -344083 806382 125797 411124 -77128 796216 -724526 -364014 -117190 -48401 -69052 -477415 346989 722234 -314352 -729540 71920 901039 276149 -741094 202929 126231 -941549 184387 -531200 -228943 305526 -594726 -448206 998411 982402 630131 -768512 -574367 944017 -237321 -32191 -575922 -125478 673880 39307 -946110 600283 -565297 903861 -289545 -817781 -969527 690794 -325244 -178668 -565140 467681 369053 696705 324841 907775 -317908 -636774 161265 869204 436211 -304796 105673 820936 633826 -77462 748062 868213 -254467 -51362 313336 103793 512191 898584 -616534 -771913 -150890 331025 -190595 -632367 -975828 281215 220182 -184166 562347 -602842 361352 -199058 -583653 647905 682016 -12662 772481 -953277 992360 95232 613773 -997877 176749 175953 -465508 -469021 -175323 -91759 -483908 372446 732992 402524 -148895 -837414 -474386 26505 708598 171572 95343 94434 33641 424593 -830149 273922 -323712 -151921 -254082 245784 416028 -134200 778957 897455 879543 -61495 240128 -67320 -479723 -627520 798001 458925 606554 129656 -117072 -604130 951550 -508696 -136299 773376 -58609 -377044 -482756 116716 297178 -872334 -658717 386628 -720743 -547446 874428 -327162 87360 637304 964458 799311 266607 312384 688839 -772427 661476 956223 -980889 443977 87357 686471 -985372 876879 382396 -558119 -430683 675998 -978764 -930218 822883 319317 -961424 -798728 -134030 -937155 229039 378411 -42050 -414129 -731051 -853929 -54632 874864 975128 -263043 906689 -637252 919512 -242497 -59582 213079 854235 841319 138253 222490 743610 -466051 336477 55889 500734 -729716 95170 954955 681621 -953066 -255252 -10238 -946254 -210456 -913835 -224345 583237 -282023 566221 -225115 86146 557799 293300 594501 -471004 152523 -262897 -235808 590344 842656 -108506 -62358 509802 170057 53037 -597915 550292 -64917 773056 -410973 40852 -546781 221723 13610 207665 885619 -183233 175687 196540 -639848 672808 -920995 7244 947586 -265405 850815 996589 716584 -890427 -748607 -862034 48687 -963420 -628945 262882 -816329 -374332 833830 880476 206544 180256 -678725 -472925 -206089 -265180 -18112 993741 -456003 -198929 -234070 104247 -58661 -58657 -321771 -372053 -795901 171770 317516 925351 760301 754945 218554 -518724 121838 992982 -893620 -885623 787545 -889392 437811 -816252 -667582 509880 288851 307882 -9582 -899129 238961 988372 -876144 155147 -104570 -370934 927832 76649 279496 -505366 889396 -11545 -593034 -225984 -793958 -901070 290739 603365 854779 -338722 767153 183484 -559556 525757 -959474 -438608 984612 -529511 -828300 957027 791825 -452082 -279720 280108 -954850 -354851 -364838 -978334 966721 -890586 21029 298167 -211606 -425593 -499528 424795 498603 -967449 -450838 922011 -507183 -785948 -871526 410260 -695608 -288817 675000 898946 -102310 -176359 298851 225609 -57125 378422 -832095 -654676 -266936 -332042 -473603 -250173 334913 -631396 84616 -499765 -354355 651340 -517290 222016 -177368 156827 702910 915665 -903573 41016 -976983 -612956 -351558 577300 52940 -563534 -744964 435237 -759691 -182329 -326780 -772428 600330 -915202 466996 -441469 928520 667087 -923093 252616 181748 275196 -313622 353584 58083 561298 -35799 747874 854291 962681 -569555 600739 77891 -170042 581625 -582678 -629236 -539660 697204 580504 -418726 355064 945443 125423 116047 879421 -443491 272169 -371687 419541 -259497 725126 -707101 287775 50459 -189224 778569 830655 -355521 389239 693930 -736860 -269592 -296446 502943 813030 481119 845613 -418716 -661612 -461829 630162 -587325 -898573 -874792 537865 857010 575800 855113 -952527 -431518 -293289 -643522 -552382 79537 232921 605503 -506502 21681 -610578 -616127 -254835 -188428 -624211 233654 950150 -810348 -68124 -99463 -570154 -886277 -467528 2455 -215003 505147 -221644 -680244 -843262 -432232 556647 558584 -884998 47780 199898 -640705 962247 265003 61014 -18624 -916854 -802407 758874 -946592 -699872 -369360 -935949 576131 955686 188992 510545 806511 -759444 -675428 889603 343563 -325823 -203666 753465 600320 -229572 -803185 850081 -458688 -360902 -450056 -484550 -228913 518516 -738276 -940272 894990 -96778 750439 71112 111201 866756 410572 -853777 55289 715105 -757844 -754876 790430 655056 745423 -158926 197635 677261 530014 935169 -296907 -484828 657389 447551 -886202 296434 -965456 -705037 737274 913123 9941 -502696 -868849 -231633 176554 513784 -854949 -422151 6989 996315 797558 851482 184093 41588 -360330 -836586 -253128 612993 578909 -584783 -436624 -709126 212964 117432 806269 544355 -556480 195175 67227 -85292 418242 -228339 157357 -330094 781225 655473 428218 772401 973650 860824 -604933 644834 87644 -171878 369398 -909989 -757841 -423237 -877824 -681137 -775021 647282 -436758 -476515 391428 576725 803808 206955 -681467 420520 664690 213426 526970 -163100 671780 846376 140404 -185843 -720195 -317881 431224 -184546 970823 -72755 -132326 -294090 -826273 979915 -668337 171720 27858 -782397 -681417 -759707 895932 -98748 130673 683550 467378 -57913 -903379 892330 789429 458755 723530 952173 773548 -327384 -766246 167402 865348 942891 933780 975574 -751343 -633066 932054 723808 -370710 668777 -586963 614780 792869 -455358 639292 586214 111743 -966630 442021 -121875 -58117 -604177 -190598 89685 -813612 501229 794915 29265 -299774 -887309 -385955 258370 -376436 287069 797508 860968 -830730 -569315 -351078 858920 473467 309059 575861 -252708 659848 -430876 -129712 598404 35933 626715 741495 -549084 345820 -76743 780245 732065 253972 897462 552945 -709770 -394383 499593 -869199 -776426 -747277 820709 410667 397408 456911 -761625 306424 -523425 876749 -875851 -268548 -190142 -300572 3402 -206669 -750500 -725385 -487238 828269 749074 162257 -318237 -409097 850703 -107315 -523337 -70509 -990575 127106 -692817 -398389 928401 715653 -908311 976573 618591 -368174 317524 112519 305753 -355378 441157 303585 -219025 211151 590865 198034 981307 -297258 -689462 605313 -33751 -489794 -233045 -15722 244919 154458 321443 -330384 688955 442459 277366 -697545 -905632 -250440 809470 471514 891066 -927242 -300 -931107 -702607 -513523 177973 -742948 431273 -842688 113564 -961649 23887 -382573 -539393 -624205 693422 631805 80451 -89235 -212985 -880489 692716 202896 606206 -967586 38103 783566 -788351 596391 -422275 304440 262018 -947805 950477 485395 973851 -755314 197358 260702 334228 248689 152445 -702736 585786 40154 -486181 -357879 -115673 158058 473353 -131284 720824 569544 -398156 415323 659264 914108 335211 678307 952378 676832 622334 612929 -737209 570146 943503 -553899 -678792 713542 -997951 343442 244676 446463 -962037 -370718 -360838 -934631 -647498 587400 -916331 821059 -424965 -246945 -898538 719436 104770 652477 260724 567416 231339 -789018 993271 658957 -946715 304659 -767947 -828544 533429 831266 -434472 645084 -706818 432347 614357 -448656 946366 -287315 645713 796828 -792714 560045 -984238 -701816 541940 668957 361166 -13369 593691 585188 315489 472968 578485 113376 92955 844831 -596593 -188494 -647521 763226 128836 284756 795678 877796 -758103 -731362 -141102 290299 -605984 -891485 -972009 293097 285025 449060 -381066 -732721 -349945 285133 -390120 -63893 -887482 384610 477276 -214149 431986 660651 817851 892554 584822 474163 704101 43013 366322 80608 -29233 889883 -933651 -475304 -256518 36937 477460 557451 -16730 -307755 965246 373969 -781412 -599808 -405860 244317 746363 -78005 -871043 565735 715292 342410 360530 204098 -391015 432544 -509825 -979200 772132 -51688 560723 -146751 -811876 111049 581966 16387 -49980 -725516 -87006 -670538 -249971 -703798 762566 410837 -10654 453377 247581 -957088 35822 57577 132540 655156 88652 -973192 440178 676776 168208 -86845 94691 624751 444156 275915 -411708 -916688 -853830 399878 -669328 -364072 -506121 94651 351263 -165907 -244222 182159 165031 -85639 -14962 981190 -462215 710721 227311 446286 -995349 -654834 640677 -456500 906928 -245718 -759548 126959 -893913 85195 187116 -70591 -499708 -745776 524785 598063 -848701 631403 -912634 -507687 -881036 -674889 -938413 -140485 21833 -479118 -993762 -27717 -406860 141681 269780 721869 -347725 2106 -999265 -873611 587433 217702 245721 941085 426373 -283065 -125240 -226684 222669 -237224 -418872 -72465 994358 722787 -567347 -873411 -503975 928963 -384946 437172 -208778 677486 -922771 894000 504277 862751 -471517 -46704 -741154 362271 223425 -385388 -544438 -881753 -34730 477987 587729 -200526 -737345 198402 110021 500891 148567 -159327 -43216 -588472 570593 -617415 199948 148871 811366 -47824 -97828 912917 -436371 372383 -452857 -205158 -67213 60149 536446 -893645 -447880 959110 -683175 890351 220139 -888669 -289911 -580903 680406 -640259 596756 151343 470940 -600607 -728474 -103777 906091 -27278 -534796 -886959 150185 615339 57799 937650 -121006 719466 -847837 -39522 339505 605286 -141018 -875358 -309757 -111815 969121 895889 -770291 460383 221236 94951 984438 71429 5551 -730552 376473 543486 675538 -542619 700996 -748685 625531 -745459 520464 242933 112341 -324295 -56195 -524027 -480354 734258 889437 773793 -982267 -941061 -862322 -517023 971794 -733770 -156546 253641 485878 895015 652984 -234583 -924158 -429975 -567859 510575 679180 -279473 -902897 332922 -230145 138362 47848 390309 541077 280274 186720 844313 -290705 508698 117633 641205 226445 -182507 703480 316745 -652420 497271 831186 532808 -942104 267649 -904376 236826 -594112 -265455 -208059 256985 987665 160637 -732805 -235138 -426285 330947 -316583 -664077 42577 420168 -207897 -825740 237999 -549943 -363293 -238815 95019 -945183 961806 -992871 -677645 490958 -670759 94098 544187 -746072 76803 898389 -107439 -724895 -253249 274440 935649 551258 -764816 -162926 981992 -123625 -125595 -382144 -982148 357662 -46743 -72274 536285 924144 567919 -543693 788929 -167456 -887495 784795 -31852 -617699 374252 -105133 -862139 755133 -382253 -884188 -579164 944127 234294 186242 103349 259371 -612481 -867408 -420150 -741625 -991069 -624859 938291 976294 -106413 -337499 261621 -206322 -835773 -392268 -91082 112374 128947 638591 352605 -285230 -186875 -793891 217320 -520690 412218 961358 -233125 -27862 866463 216548 -876247 19871 -741692 836723 -742336 -806359 -545981 973291 -29590 -36886 738696 -30196 594092 -761222 -931373 348217 438600 590834 -351163 -57695 -713949 113379 -176964 805875 -741925 -906285 -410075 -523062 -953368 -758400 269391 888011 -104642 -56773 652577 883816 -793234 850826 -314650 -798735 -164544 -220141 -261083 615508 -184355 -905625 166872 135777 -256960 -986743 425360 694826 655273 -891250 -962347 -90811 745840 73303 -574647 -888212 717939 404777 653754 -983587 -970076 604767 671714 436047 -50263 -224771 506403 563433 -960488 767093 -230315 5333 418867 -605043 594172 977969 -277767 514971 70919 637685 -160620 563856 -224414 673445 492233 -571415 -276756 964924 -112627 -65377 385363 -679649 -868346 581092 -73382 70188 -724163 -623249 -317368 -567476 -967856 -698333 412480 496269 -802391 -440284 -596298 796677 -424920 849135 619109 -33542 -806978 588197 633181 -378722 -84395 901307 485893 912488 -993921 639758 585427 -409896 -468086 175298 863406 592472 -523810 -660206 -955913 423164 -755325 -834863 838278 156511 -916922 -195467 -728537 -698406 241133 -77118 -685433 -77873 91080 -419110 320114 -20893 -503712 -50060 742632 181346 -988373 302034 178816 620704 639114 391439 -265255 541729 -180342 11431 220710 831394 315698 -392947 192731 -546682 -48628 -393397 83514 -713750 -207667 662032 -41919 744606 529415 878654 202390 142984 -841018 -666295 810940 224804 890288 -20670 510737 -940077 -993478 -785501 801548 408426 424723 -421512 469611 550098 -530907 499277 -202930 591560 351366 89715 -558525 -526753 -911448 -383438 516708 849852 -971169 286604 -120303 -885250 -792362 -772758 652783 -7346 881159 774128 890816 -784528 617693 380600 825521 -144907 112013 207097 -370478 889752 680906 -363361 -828613 -429146 -527847 -353365 297435 911900 -846157 -178701 474050 -233727 240512 616795 -194007 -744849 953411 -817704 -422823 -904571 735681 -216947 -623787 877743 849534 -466252 -986065 908801 -238381 932321 -764539 130250 -275407 637902 -968153 -59505 -577655 313016 611022 866076 -830703 -684074 601214 -308797 309703 269645 216511 393548 78648 120227 -211936 -632731 -133032 -775446 35155 -77165 -422927 -841149 793978 357970 -558109 330745 -534715 -143345 -563496 -118152 -744801 33833 102763 -623860 -993177 525784 -752994 588520 626600 -615829 -627207 938544 -963225 113098 -283925 544382 -178459 -23911 564499 -776150 -44813 -118238 95844 -526658 -902134 -40641 -477948 -896954 -428278 -523720 845239 -399433 -876073 -718115 -378901 -561617 -73401 271854 339880 261719 -920802 354004 -360192 -276408 -800959 -552214 -747321 -301301 -862910 -186833 49913 -608538 132172 455156 -815785 775228 -872799 -77816 639531 474458 -351221 -887261 -729402 178679 -799350 611480 -485074 -536671 763791 -733082 424770 30530 -564939 -40390 -319726 84023 443776 846742 232356 -527843 -500952 903982 631003 -998259 892475 303275 -484627 -805447 345407 891384 -354413 809266 716629 -217634 -203999 -17831 -29780 -170806 154101 942099 -474137 539074 42809 -451433 441240 884930 551464 682738 -676295 -218686 481512 -824640 235439 887652 273145 427087 748047 741357 -264898 703228 779002 -279294 -812426 60693 617213 -385698 75217 -261229 -243799 -944503 -87502 422565 908840 -762967 -831815 788010 53475 423719 625265 -394668 840411 -197971 644686 767952 -381056 -897138 -76616 580499 514360 -760056 -17364 -10574 -850589 85388 -575325 -125254 -889297 -760188 -292010 -613063 869223 512476 -17170 785574 -664840 718422 -563694 454145 190027 155080 455109 557358 461210 -617484 -322388 -966508 -593243 -269426 -842393 -693267 -825214 55200 -143775 -282538 -822728 331445 -490146 161357 398348 -14308 365288 -700844 492751 156215 830135 778062 -859126 914313 830446 -41498 -419446 709496 656247 -665863 224951 -775355 414337 739177 92058 -902370 629874 609884 342848 -34812 -562546 148216 669560 437803 181085 176089 -540314 -440201 -978909 585317 159849 844798 132956 410235 91480 -563844 -923248 586494 148837 -48094 -38844 234440 -578948 -997272 710497 629803 869385 -342099 -942695 -424051 728215 -684991 -335087 178360 -551525 -967524 -428386 -6088 -277137 964935 377426 -900635 -606805 608536 -221391 43992 -563987 -838293 -330831 -598284 -340987 -722344 87077 251317 -26191 543056 -144289 54913 -859977 -594837 -392245 -140514 -864467 265824 -365367 -282931 615906 -402255 992644 -708982 571768 820105 -25808 -680272 -630068 827069 -809182 -604829 659778 -859485 -168691 -671827 -765587 -545005 -946801 -951850 -673992 441096 -794135 -412243 -601832 -318020 -710327 526417 998130 422630 183291 -646837 -266068 -971064 -953353 -98648 707913 439572 -760425 -546402 -553705 -778662 -172982 265820 514958 -300688 156060 230395 -835289 149413 336122 793367 -387710 -863893 -635337 231705 -627137 -638922 982460 -836169 190597 720526 61973 -128878 962870 -826789 -883530 -712686 361137 -30403 679454 -876428 -490173 -423122 182513 957351 -108810 -738675 -465748 -668483 105200 240436 517084 339684 353669 -404125 -961747 856108 491740 -644597 812541 -790397 105420 -159580 -751331 -348238 920490 -889335
Output: -445940

Constraints:

1 <= k <= n <= 5917; -1000000 <= a[i] <= 1000000.

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