TopCoder Statistics - Problem Statement

Problem Statement

In topography, the prominence of a mountain is defined as its height relative to the lowest contour line encircling it but containing no higher summit within it. In other words:

The prominence of each tallest mountain is equal to its height.
For any non-tallest mountain M of height h, its prominence is the largest x with the following property: If you start at the top of mountain M and never reach the altitude h-x, you cannot walk to the top of any mountain that is strictly taller than M.

In this problem we have a 2-dimensional mountain range: a polyline that goes from the left to the right. The range is described by the int[] H. The vertices of the polyline are the points (i, H[i]) for i = 0 to N-1. We assume that these are the only mountains in the world.

A peak in the mountain range is any point such that from that point we go strictly downwards in each possible direction. (Thus, peaks correspond to strict local maxima of H.)

For each peak, calculate its prominence. Return the sum of all those prominences.

Due to the limitations of our current platform, please use the pseudocode below to generate the array H. The symbol % represents the modulo operator.

for i = 0 .. N-1:
    parity = i % 2
    a = coef[3*parity]
    b = coef[3*parity+1]
    c = coef[3*parity+2]
    H[i] = (((a*i + b) % 1000000007)*i + c) % 1000000007

for j = 0 .. idx.length-1:
    H[ idx[j] ] = val[j]

Definition

Class:: Prominence
Method:: sumOfProminences
Parameters:: int, int[], int[], int[]
Returns:: long
Method signature:: long sumOfProminences(int N, int[] coef, int[] idx, int[] val)
(be sure your method is public)

Notes

The reference solution can efficiently solve any array of the given size.
Please use 64-bit integers in the code that generates H to avoid integer overflow.

Constraints

N will be between 2 and 1,000,000, inclusive.
coef will contain exactly 6 elements.
Each element of coef will be between 0 and 1,000,000,006, inclusive.
idx will contain between 0 and 100 elements, inclusive.
Each element of idx will be between 0 and N-1, inclusive.
Elements of idx will be distinct.
val will contain the same number of elements as idx.
Each element of val will be between 0 and 1,000,000,006, inclusive.

Examples

7

{0, 0, 47, 0, 0, 47}

{}

{}

Returns: 0

H = {47, 47, 47, 47, 47, 47, 47} There are no peaks. The sum of an empty set is zero.
8

{0, 0, 47, 0, 0, 42}

{}

{}

Returns: 188

H = {47, 42, 47, 42, 47, 42, 47, 42} There are four peaks. Each of them has prominence 47.
10

{0, 0, 0, 0, 0, 0}

{0, 1, 2, 3, 4, 5, 6, 7, 9, 8}

{500, 300, 400, 200, 400, 700, 100, 300, 300, 100}

Returns: 1500

H = {500, 300, 400, 200, 400, 700, 100, 300, 100, 300} Peaks correspond to indices 0, 2, 5, 7, and 9. Their prominences are 300, 100, 700, 200, and 200.
16

{123456789, 234567890, 345678901, 456789012, 567890123, 678901234}

{7}

{890123456}

Returns: 4543586810

H = {345678901, 703580362, 308641830, 493672669, 259259064, 938077051, 197530603, 890123456, 123456447, 789822019, 37036596, 197162605, 938271057, 258815266, 827159816, 974780002}. The peaks in this mountain range, going left to right, have prominences 444321298, 185030839, 901040455, 692592853, 666365572, 679455791, and 974780002.
1000000

{0, 1, 10000000, 0, 1000000006, 9000000}

{0}

{20000000}

Returns: 1000017500001
1000000

{0,1,3,0,1,0}

{0}

{1000000006}

Returns: 1002000002
13

{0, 594466506, 487125379, 276411073, 415062492, 421352827}

{1, 0, 7, 10, 2, 8, 11, 3, 4, 5, 9, 6, 12}

{999327372, 817537, 999272885, 544629, 651057817, 673673332, 407879373, 999265435, 970732, 156449, 999015928, 587328861, 843403}

Returns: 3079328766
4

{0, 548934239, 872583032, 840026799, 392537040, 986210305}

{1, 3, 2, 0}

{481789, 999290232, 571390, 729053}

Returns: 999537496
2

{0, 43901203, 828718827, 582239740, 411998379, 73514838}

{1, 0}

{76321, 408014}

Returns: 408014
2

{536148941, 676216947, 400720810, 0, 430015013, 109637006}

{1, 0}

{412913, 999127711}

Returns: 999127711
15

{589756569, 729166753, 985501755, 825313015, 688723784, 337321499}

{12, 3, 8, 5, 2}

{572481, 789475, 944458, 999836234, 544714}

Returns: 3685906839
15

{468195242, 781439377, 526842172, 0, 350506113, 52690485}

{}

{}

Returns: 3492043976
5

{830378227, 133179045, 103394234, 469391980, 0, 358312655}

{4, 1, 0, 3, 2}

{999850335, 361470, 117346907, 333903229, 653879906}

Returns: 1436812449
8

{0, 0, 936164376, 0, 958920515, 819342377}

{}

{}

Returns: 3744657504
8

{0, 724900465, 998965079, 547838932, 40598036, 952049656}

{0, 5, 3, 2, 6, 7, 4, 1}

{781652, 999642217, 912898, 179749843, 568291, 863723, 759365, 998550953}

Returns: 1997729237
9

{0, 961925421, 975155805, 662212723, 963663275, 866417028}

{}

{}

Returns: 2604138572
16

{439933264, 650222602, 197011876, 0, 868217808, 846173433}

{}

{}

Returns: 2917196183
17

{368811557, 596705226, 324151370, 423562100, 38178810, 669734590}

{}

{}

Returns: 2513975239
6

{421315870, 897479257, 947036521, 0, 36450493, 394889797}

{}

{}

Returns: 1323154180
20

{0, 0, 279584623, 171791451, 922606452, 42708358}

{}

{}

Returns: 3396148083
17

{158396353, 275044379, 355156688, 705675087, 220653916, 968931231}

{6, 15, 8, 2, 4, 0, 10, 11, 3, 7, 16, 12, 1, 14, 5, 9, 13}

{63742419, 999323389, 772385, 828968, 999277692, 62248, 274942463, 999528551, 550743712, 508918, 999333985, 999541347, 654921847, 893378, 673562, 999598105, 219917}

Returns: 4439241567
20

{0, 256920389, 809231904, 0, 0, 746135704}

{}

{}

Returns: 3176931849
11

{0, 635579721, 928536537, 541555155, 802433616, 833335012}

{}

{}

Returns: 2817353279
13

{0, 709487332, 780723745, 81103305, 0, 419704490}

{}

{}

Returns: 2262554361
16

{667432712, 848584236, 686573551, 869734475, 358398435, 303088382}

{5, 15, 14, 12, 9, 2, 1, 6, 13, 3, 4, 0, 7, 11, 10, 8}

{999666944, 431034015, 187764, 192209615, 52623, 338394543, 422147, 314453, 280633, 97345, 999241252, 601999444, 999974373, 999247401, 999873722, 999187829}

Returns: 4369868709
7

{850177816, 310477149, 312925620, 0, 975807843, 40733571}

{6, 3, 0, 2, 4, 1, 5}

{999160677, 999505497, 306762031, 274102, 419878592, 230001, 860849121}

Returns: 1885319612
999771

{0, 987660075, 311456702, 0, 834892398, 316968557}

{712708, 523652, 267744, 401872, 751414, 231601, 206508, 111464, 217399, 898161, 317121, 581868, 12761, 930571}

{731971, 210390, 795546307, 25448690, 912227, 999238595, 384607, 262725165, 999388487, 885282511, 999195492, 999624483, 233275, 826290732}

Returns: 166644248760059
999416

{248927732, 980906547, 822121572, 0, 663800371, 550453667}

{13552, 726038, 697220, 56487, 228077, 202759, 419356, 274701, 516154, 982191, 321283, 421679, 733945, 545047, 12307, 572253, 910007, 404556, 329506, 878458, 146749, 502642, 112244, 639278, 374576, 802638, 2159, 759682, 570208, 251216, 529367, 730209, 929010, 309941, 225566, 522594, 799191, 55360, 534662, 356159, 515100, 379437, 640757, 196627, 657278, 706931, 409829, 877321, 438935, 233232, 781635, 887369, 462461, 616470, 577269, 160333, 393769, 544275, 549626, 743900, 779546, 655047, 229125}

{598871823, 190588, 249946, 999812398, 999447649, 754253426, 999727141, 913794, 812376, 550377765, 340427, 230697, 999777615, 999142319, 178054, 943232848, 863698752, 999001963, 548756, 209708, 890534, 999171527, 999547063, 455601, 495293, 457235, 22504, 625450003, 999418245, 598651985, 65053482, 723356, 222852837, 999197436, 936219, 847690669, 940585, 17742396, 999271359, 999291760, 978162830, 691241, 385260198, 999009488, 999599203, 999918753, 999194651, 277800698, 999488474, 528282646, 34363, 999672692, 739757410, 220247, 999205698, 777436844, 150163, 532004561, 780879, 312032389, 668741, 718683, 796665}

Returns: 166551204863884
999881

{0, 208486131, 40580456, 0, 811870054, 277548715}

{956490, 598522, 174903, 348867, 899654, 153999, 856241, 955968, 903388, 333041, 711141, 833619, 696671, 814929, 557657, 848584, 942584, 715642, 781408, 391136, 948454, 388295, 150345, 963855, 449051, 109689, 19867, 133254, 426489, 393316, 890207, 188542, 875517, 634295, 445103, 957595}

{999254588, 999279326, 47483763, 999946060, 190332539, 562056353, 999322708, 999752236, 999923533, 394685689, 822601, 630514, 999668163, 558633715, 171474, 664869282, 571780889, 999241157, 999437857, 999005617, 54762, 999647256, 999097306, 667150430, 999218855, 999358631, 126569, 159382, 472526, 999609609, 999212040, 999967900, 999705046, 999262108, 999186002, 429181}

Returns: 166647926044367
999397

{0, 0, 347434840, 0, 72385970, 125070530}

{}

{}

Returns: 136556738195631
999245

{473753261, 664967025, 103078065, 0, 357689261, 304566467}

{489568, 784405, 261292, 798696, 309359, 852869, 277780, 954026, 92209, 48344, 405902, 252714, 847673, 94195, 699513, 165702, 269563, 505927, 170805, 443720, 965823, 390715, 357285, 126529, 530566, 990617, 392481, 756276, 612782, 382795, 562237, 708668, 466954, 634794}

{835796, 524697, 286251, 185429, 900682, 676421106, 616883, 999910405, 311957, 429606, 612117, 999346684, 302384348, 730964527, 353239, 999861896, 389980, 775224, 146815373, 999538879, 498497119, 586203990, 999934094, 999093799, 79149231, 440057, 898199, 718829400, 875516599, 486462815, 229317621, 999707473, 999201909, 999734240}

Returns: 166442122562467
999072

{213153573, 0, 21506175, 603604606, 408664791, 13619271}

{900137, 385596, 986764, 434523, 270194, 38148, 765719, 733637, 169050, 36187, 988868, 899334, 850946, 49453, 507181, 188297, 925880, 243176, 958914, 919228, 758908, 530825, 367876, 865973, 779196, 133593, 31946, 483354, 664516, 154686, 415503, 24391, 624744, 209249, 757720, 441419, 203194, 617700, 139746, 465218, 316609, 677234, 261989, 265221, 955006, 372622, 12470, 819269, 702920, 405473, 469465, 900171, 221116, 817048, 173837, 888945, 727065, 916623, 782779, 836668, 150144, 851067, 766458, 870110, 192893, 360173, 558125, 162712, 52865, 412127, 374650, 114078}

{999509619, 999834126, 999621690, 954827283, 447762947, 920339, 855305, 487207, 999388586, 999178743, 680271, 560541, 533071569, 999813717, 48681, 999909246, 999654603, 864221663, 999256494, 98693734, 999996849, 395475, 227669, 999024746, 999260645, 354859972, 614996, 870314, 18690799, 999742793, 547824343, 350575, 568793, 999362357, 535708, 999828662, 36665, 624375, 810043919, 222264355, 995145625, 999604778, 999401006, 823354, 29245, 559485814, 805230, 381234, 928564, 999273572, 999966324, 999725300, 533793177, 701916, 133561, 841641, 564803, 987285087, 999296529, 650631618, 999382081, 791815, 406587, 654052, 661734, 832961, 999962979, 856419, 756336, 278865713, 999503421, 999808911}

Returns: 166464329836483
999575

{170686110, 997806213, 878963227, 440166964, 61799647, 953839293}

{}

{}

Returns: 166476506704104
999507

{0, 674725870, 859818145, 764103376, 891767216, 555486530}

{226447, 919566, 427409, 134787, 605563, 93602, 73443, 278953, 33325, 331295, 734205}

{528591932, 217431791, 388071296, 972493185, 999070278, 728517, 66551, 999851568, 222057, 70080783, 71323395}

Returns: 166437411066350
999872

{0, 197661376, 618120387, 0, 803425309, 594040362}

{}

{}

Returns: 166640031738477
999412

{0, 182182866, 209681724, 0, 99461477, 290586284}

{}

{}

Returns: 166566383868956
999825

{917031342, 241723477, 521532073, 0, 668205034, 548761848}

{181955, 92987, 647419, 566471, 176032, 4868, 808519, 795891, 301859, 855540, 125302, 467399, 592593, 946109, 779081, 565074, 199972, 853211, 846983, 540218, 335401, 696092, 931421, 419430, 536964, 44247, 755823, 298311, 939565, 458451, 815240, 311557, 317805, 743454, 93003, 855298, 920158, 580618, 627983, 607563, 675132, 520475, 324174, 86534, 851461, 673652, 406398, 210480, 884189, 322789, 231033, 359881, 548530, 617297, 604278, 160488, 491494, 207569, 4537, 344642, 857565, 982990, 846813, 653980, 360357, 957609, 256700, 639220, 815030, 42458, 551782, 584414, 769727, 741651, 168029, 54839, 796771, 824060, 32580, 516833, 314780, 632140, 457583, 847212, 401432}

{999480611, 911519, 172096, 531699, 999635749, 999103049, 757035967, 578100, 157124250, 999824240, 324659, 986768, 427335, 999531425, 999692480, 531489, 999525900, 545010689, 999184037, 999632753, 126223012, 804163, 999395187, 239983107, 999727886, 159750513, 895750636, 188829, 999896032, 999682598, 999295050, 631297, 486487470, 999917149, 24142, 755485, 38158, 750441715, 650884672, 43634181, 586024445, 954435729, 936014, 15409548, 996404, 323890271, 502381, 88462093, 627784, 649404, 278413, 999195047, 234549572, 999888149, 807231, 938871323, 624584, 522308, 21800194, 999717055, 999029327, 536315430, 999217080, 806886, 622619125, 999339527, 999378205, 907913, 936231604, 999434360, 506604, 260105, 999962683, 999351171, 999553092, 999857807, 999642299, 999464488, 160728954, 258984, 375810, 918137929, 328725706, 812270992, 506999}

Returns: 166697089956801
999334

{0, 3734417, 426585471, 0, 293101351, 579759863}

{322970, 833169, 828482, 547788, 439147, 204274, 520848, 638047, 61363, 671681, 770781, 769866, 452228, 314268, 132880, 104404, 33843, 523653}

{966876, 290112, 440966, 184742, 116311, 5943, 999930881, 562640, 391617, 94387, 694570, 210613, 461703, 566043, 889714, 777351, 162184, 647209619}

Returns: 166562879185253
999360

{686046722, 399595349, 453037194, 423638984, 194144105, 221039828}

{}

{}

Returns: 166451986186957
999975

{580947997, 275029900, 451597665, 887506634, 282867948, 885163794}

{387269, 25890, 984765, 400387, 120476, 130899, 270028, 525481, 406376, 405354, 750161, 416032, 56704, 646800, 360177, 176714, 927835, 129959, 718230, 237237, 678294, 340605, 46560, 381473, 742337, 684067, 847911, 818858, 565086, 402171, 307692, 801260, 288952, 624224, 433088, 657291, 751446, 236585, 561425, 388133, 879692, 701529, 37898, 407214, 448243, 975653, 54656, 839670, 462191, 811327, 983453}

{999838875, 7990, 999465775, 999341145, 389620198, 999883194, 999866748, 999245701, 999936147, 746145, 999428147, 869075626, 200768, 999773645, 63025, 995916, 423858902, 290549717, 999115250, 55677359, 307684337, 840680, 505516849, 716489, 999537102, 718365, 268155771, 999758821, 999449692, 596129, 242834562, 999316084, 163140832, 999709125, 211270959, 943828, 999506089, 443868, 221509, 999264572, 411035379, 396777, 999839498, 540750, 713403, 819787, 906105, 15706438, 999848732, 999075674, 805791552}

Returns: 166906516436826
999259

{917099412, 164137486, 753486683, 0, 203646745, 225655914}

{}

{}

Returns: 166274973461643
999442

{133702002, 316575274, 698590863, 536177335, 0, 29713091}

{457386}

{111473885}

Returns: 166473352823490
999550

{805627638, 475892901, 311041826, 957201720, 444565303, 860850161}

{}

{}

Returns: 166756031868082
999454

{0, 526058626, 942305865, 0, 63679757, 809511782}

{697015, 129330, 715406, 71956, 489570, 632515, 699043, 947001, 282746, 925220, 567711, 678269, 38140, 770969, 987686, 526340, 476864, 490749, 602742, 832811, 486408, 888805, 12030, 996503, 329484, 544404, 226294, 259348, 72132, 60149, 464214, 515123, 868317, 935863, 598023, 465536, 735644, 666170, 536972, 701358, 640163, 575511, 700132, 382601, 390396, 331597, 209762, 29930, 143934, 285818, 419624, 597949, 977081, 184921, 789041, 556989, 343482, 804492, 196907, 869658, 469419, 294675, 880979, 436068, 462880, 116606, 797698, 759534, 922508, 257962, 724029, 519897, 101024, 334827}

{430726841, 999274975, 808835, 146753, 999668689, 737050623, 510573, 855814890, 472493273, 808593, 848743613, 763894384, 715909, 38270124, 661223, 962646821, 336499255, 724116, 185842, 999730147, 999357663, 120554924, 999362034, 95562493, 999399136, 885080916, 908929, 766584, 112307223, 322899, 286098, 172360, 361917, 312157, 999722108, 999005535, 999014000, 314367, 999153467, 999868127, 353987195, 999471657, 999556695, 999133121, 362742, 126351013, 797157034, 778543, 999306618, 999666553, 915316486, 704394, 125832, 766034, 642483984, 999550325, 999386174, 161325, 420052165, 768406, 629881, 999194146, 999830329, 214582, 2981705, 999214868, 952082, 854240407, 339988, 622639877, 75868264, 547224527, 519205479, 999818647}

Returns: 166584341812900
999568

{0, 370523485, 758226973, 11150148, 351814463, 458153767}

{}

{}

Returns: 166630202262135
999156

{0, 122940195, 305252981, 577199363, 75504806, 56008515}

{}

{}

Returns: 166692608421506
999639

{0, 57073100, 631461239, 0, 122386964, 478213357}

{}

{}

Returns: 166611330982343
999603

{226173280, 359087172, 804371706, 0, 370644966, 65411320}

{795094, 542755, 953915, 317931, 13835, 334767, 891440, 826854, 486932, 83830, 504127, 597241, 947074, 159186, 299209, 457006, 278339, 712145, 886675, 599473, 249294}

{773970, 732161845, 925707502, 568197278, 999807886, 247110, 414852270, 999684616, 999367050, 293160, 999266429, 999266113, 697466, 691665288, 999243226, 622402, 798193, 768296166, 999998581, 809322434, 536098}

Returns: 166618478119003
999906

{840418470, 0, 479525610, 0, 0, 988911868}

{638773, 778991, 715758, 688480, 907398, 26344, 216419, 888255, 438301, 287759, 413333, 512043, 79187, 111961, 308474, 579720, 699480, 537404, 352798, 209787, 440620, 187993, 252985, 744099, 906545, 945386, 119150, 837125, 543170, 243751, 189283, 89991, 89275, 171776, 785250, 533071, 376022, 280308}

{999047786, 288736, 103880607, 805737, 403903, 494452, 999527187, 267469, 999471138, 999692685, 579027, 672326999, 999418110, 999100297, 788390, 650252, 999141332, 493449, 745753551, 814151, 369222, 314391345, 999913543, 999168789, 140674, 999763852, 260345976, 779376, 999628646, 999284151, 480661561, 300016712, 844670108, 167449, 643985, 23532, 999478661, 999214823}

Returns: 455571756379423
999457

{0, 461582348, 958946711, 0, 247280769, 365102463}

{}

{}

Returns: 166581259090075
999161

{962268262, 453410373, 623051400, 344980722, 373527040, 976835109}

{192966, 102234, 613293, 169855, 509276, 131784, 634479, 166994, 219326, 275979, 672693, 566742, 143966, 767611, 549909, 212835, 466889, 183496, 321948, 296908, 967220, 946834, 451417, 33368, 871673, 160644, 401731, 234257, 117059, 902710, 539991, 106294, 319209, 944907, 243087, 728227, 277682, 128293, 78847, 420763, 328638, 852499, 848092, 466977, 332128, 76660, 963547, 59899, 518191, 364270, 807253, 365313, 240797, 754175, 169872, 268258, 336132, 271710, 788298, 447781, 166784, 530781}

{999931178, 999917009, 105513018, 105942429, 611737, 461063, 999022939, 915760, 294500, 993886, 807864, 585040, 535755893, 495105797, 694682659, 289182421, 392683454, 999713679, 999673363, 999552966, 535033331, 35964672, 668954107, 999458609, 28268023, 449583360, 588710, 999755942, 300410664, 999062307, 999129369, 564682688, 674094, 999461368, 603279453, 173890620, 999086076, 50678, 374294, 404142, 123309549, 393257, 999592009, 999714987, 999665148, 274725423, 999181090, 93937, 999282746, 924933373, 465567, 438230850, 832675, 999445901, 999561440, 999522902, 546792787, 999785940, 682332455, 999666556, 1234675, 999472111}

Returns: 166606058103096
999808

{298378920, 181543211, 679263917, 0, 106543129, 881150021}

{}

{}

Returns: 166666504596385
999822

{698630478, 0, 520467463, 0, 449675741, 39021460}

{701523, 867656, 578757, 56213, 492212, 193838, 41416, 17627, 534970, 206177, 573815, 215670, 135083, 243298, 297816, 608771, 121876, 226937, 345837, 762303, 646037, 136575, 127225, 647594, 270934, 549754, 933687, 370612, 289184, 248748, 212424, 434745, 796824, 194166, 529374, 556368, 164114, 502419, 736119, 223314, 697838, 344762, 542343, 355367, 172144, 45211, 468500, 703868, 531251, 735962, 173866, 201731, 418797, 173589, 72167, 494314, 218918, 660943, 988578, 857648, 632994, 56727, 208455, 987081, 171634, 105921, 888208, 465803, 113899, 164978, 476680, 733944, 138913, 377032, 977802, 572491, 898325, 572752, 166471, 196722, 804152, 549983, 949202, 785696, 151780, 781836, 269369, 234928, 970466, 565464}

{303648, 967359, 999225746, 354882, 225938557, 809279885, 537568, 619378474, 281182102, 999230489, 622650409, 999492226, 999914166, 836993937, 999520802, 686312, 258732, 290193, 618673296, 999530714, 645113, 133138284, 999052936, 625746854, 344748, 689172, 44114, 999720820, 999498945, 819562832, 999287304, 76287, 999190631, 435877, 627183260, 682238, 82079, 999857462, 818665, 417165604, 621235, 767875, 999662072, 999024044, 999449712, 209156590, 999381216, 66766106, 43507, 439060328, 206734, 999405829, 999343029, 999271312, 274726, 999962297, 522466564, 973857734, 999267912, 830199625, 999481147, 61302230, 999076129, 999886606, 999927487, 666308169, 647187979, 809013, 999119967, 28437259, 999227228, 929973049, 985486629, 948469, 223308, 87653, 210018920, 988838119, 400821054, 836604, 999299105, 999589047, 990195, 589150398, 999488794, 999738550, 999013720, 999278648, 503656, 68213}

Returns: 166869129312705
999350

{280991457, 282973486, 516065846, 709188608, 309838842, 622216540}

{352321, 782105, 766457, 196141, 14247, 12524, 879785, 302675, 104194, 478790, 592862, 667597, 912100, 116354, 198000, 553239, 807182, 410844, 716711, 512933, 863697, 197826, 725269, 105299, 61418, 851981, 597553, 365186, 95704, 314096, 767526, 358259, 955133, 930485, 430871, 623069, 877338, 945328, 917172, 112749, 644112, 3156, 969963, 395439, 70173, 983150, 712411, 776395, 350871, 364276, 137249, 593381, 711926, 694305, 856356, 654452, 967962, 954936, 193405, 35689}

{692383674, 534236, 999036620, 831656504, 592464, 999228955, 999768932, 999469259, 54038517, 679703, 999995146, 999009483, 999145136, 203575, 965510190, 999644478, 999474036, 999340679, 245159, 999311163, 82847265, 999873821, 999702445, 992330621, 326516, 999532062, 378890, 133201450, 488055, 910151, 999587008, 999377089, 999666855, 596459, 565444471, 999248066, 999333149, 999906598, 999589994, 234211677, 220463060, 999315193, 729624331, 964097692, 999301467, 586573, 381880, 999934208, 78793895, 322887603, 537257, 999786683, 124322, 253906, 999930635, 664510115, 309739369, 999399600, 162641549, 205796}

Returns: 166684171818939
999150

{0, 0, 252180667, 248800271, 371156014, 896336370}

{607760, 528341, 458935, 695072, 841102, 444633, 448513, 276471, 749628, 648812, 792636, 503684, 977252, 535214, 459759, 481098, 357391}

{571956004, 799366, 50536204, 999473931, 999943332, 999136948, 999018724, 999361128, 999531282, 849546, 543624084, 644798, 999435309, 999048317, 330814674, 434953732, 71995}

Returns: 156446897751260
999682

{243454647, 19262191, 220937385, 613764368, 643923071, 601944009}

{394078, 599147, 786742, 982040, 784797, 734920, 257287, 880349, 141829, 21407, 318029, 463548, 115207}

{221881, 659993, 999822513, 222452950, 999490970, 539234585, 648153431, 999964759, 315357548, 999827619, 885734108, 264992528, 999803147}

Returns: 166776250249607
999496

{0, 791937648, 962495891, 160313012, 333839132, 261838109}

{}

{}

Returns: 166562656351778
999761

{0, 421597678, 952221864, 0, 500798694, 991880841}

{}

{}

Returns: 166629550993540
999138

{0, 403077687, 433336262, 426100240, 493353831, 889960672}

{214092, 187685, 869187, 173577, 137222, 462346, 417692, 425750, 331069, 480912, 710639, 429809, 701916, 599796, 395489, 85504, 603200, 871467, 366613, 768696, 778841, 872796, 576555, 913774, 424147, 520942, 570417, 38742, 784956, 972121, 643792, 179516, 73024, 398545, 660325, 778719, 108968, 712229, 207885, 535878, 398119, 101060, 787622, 841919, 190070, 355522, 863240, 605816, 245674, 575881, 903765, 135457, 442452, 881156, 128053, 881281, 808841, 801621, 150544, 345864, 673817, 491675, 238668, 850925, 557815, 609101, 383422}

{504211211, 30447, 999900639, 441242716, 715233, 999798487, 999020501, 73578, 186517, 796150784, 776218, 682344, 960912, 828095, 999142825, 671884882, 998513, 305180, 586941703, 999774800, 668722, 604428, 234909, 999224832, 163820582, 999145416, 999039681, 999193990, 933407, 999742299, 759266, 900341, 999797410, 889472, 999577316, 374986148, 999429053, 388885846, 913851867, 423710, 247933, 999655274, 999861977, 416398, 656847910, 183380, 505455679, 999915184, 999803244, 193551211, 460638, 999259534, 939064, 80620, 296022, 358386438, 169978914, 417085789, 999254150, 211058455, 240328783, 765725, 65278864, 999557216, 888072688, 999434428, 613545449}

Returns: 166402853078633
999124

{0, 898083068, 77320034, 139678847, 407761551, 457316637}

{}

{}

Returns: 166309907475636
999425

{0, 767411985, 558671507, 846963927, 0, 752225174}

{}

{}

Returns: 166615008420269
999684

{0, 478639479, 298994052, 850705767, 222369317, 367776214}

{467143, 702315, 539319, 851161, 469964, 380092, 993796, 828241, 889819, 730870, 270204, 694439, 773714, 53992, 859541, 287633, 693997, 167123, 389572, 212588, 38931, 769566, 23180, 270871, 524266, 691272, 149514, 645493, 825300, 798859, 610668, 749163, 646697, 626011, 620746, 495000, 105225, 70184, 129422, 782432, 524903, 9535, 448948, 503537, 46935, 721675, 191734, 206724, 327472, 72546, 916694, 437371, 594181, 379177}

{720336, 765522, 122610684, 430385, 729378, 135659, 999714182, 806274, 572716, 999305819, 999580612, 270475311, 781499, 304378, 999123711, 414817409, 97667, 704742, 547733, 178191834, 999652267, 999197119, 999574761, 661346, 999986103, 349593, 281665, 999705025, 999698659, 999640046, 999454934, 32884459, 999656905, 414269, 679783, 999791332, 245369, 387463, 999003204, 999548609, 333531, 999340653, 341531473, 900581, 210871, 999772997, 932556552, 108180250, 254313, 417141089, 115299977, 975696, 221570, 167304}

Returns: 166651078401932
999562

{0, 0, 433765851, 0, 0, 766102208}

{308994, 372477, 323826, 507524, 604726, 208560, 550790, 616685, 924333, 968075, 233091, 722328, 280585, 421398, 177187, 493479, 414042, 960647, 796713, 592544, 979050, 8129, 791675, 628904, 278865, 115320, 894893, 619867, 246608, 961391, 730160, 886381, 181455, 38116, 844319, 199703, 645959, 591874, 217263, 50751, 840072, 995389, 68022, 97024, 456146, 950422, 501297, 202876, 449903, 659910, 622746, 532993, 510898, 418389, 418207, 958539, 547065, 401454, 224749, 246195, 708752, 495146, 902626, 862493, 85358, 797193, 684527}

{999209600, 999053180, 339950, 548752, 999912729, 999845338, 314424637, 691750027, 954488, 264233651, 999657807, 45290849, 999236354, 163890829, 999740642, 681650, 620042, 999161002, 823528930, 812088, 999522984, 171679, 765638974, 488487, 162142, 999447667, 939023, 984555855, 604709229, 852610158, 193004398, 350764921, 790802042, 999666358, 999252225, 545784, 934821594, 866540951, 626501031, 317681, 464426, 999485750, 829531, 999064611, 248722346, 999246500, 999949635, 529706089, 5695113, 999766626, 999976740, 272122, 316406115, 999780820, 999342085, 829257779, 102623, 347276, 999095010, 200475690, 842325068, 198530, 413052746, 715874851, 256455769, 926295006, 463071}

Returns: 209661141799707
999767

{688449267, 39200767, 769352745, 330183293, 629658926, 869529842}

{272412, 461121, 816396, 603459, 840004, 324600, 761669, 158480, 601139, 414171, 851004, 78978, 49883, 219367, 67740, 938375, 453893, 897442, 745806, 970600, 590440, 557920, 141811, 365070, 119827, 836627, 573675, 463564, 903187, 962009, 531566, 582527, 339392, 235162, 623462, 616881}

{928569, 469195, 999198546, 62328, 368264036, 443876, 999961483, 999445030, 999484507, 157933, 921124, 125487, 150850, 323983, 999929777, 79779007, 448836190, 999096546, 999207568, 145922, 999700739, 678238, 488070, 999583964, 325924, 999657583, 999045287, 100610, 18938629, 952250571, 789349, 999286577, 999218578, 999069286, 524112037, 306228}

Returns: 166773548329455
999142

{396371563, 566069445, 569515673, 0, 487234236, 207143754}

{}

{}

Returns: 166782611074641
999179

{0, 0, 587860092, 0, 731622902, 118060046}

{}

{}

Returns: 140578917875593
999724

{612079165, 0, 232127956, 0, 86331828, 839754668}

{}

{}

Returns: 166594245600958
999534

{440213033, 779155330, 315622439, 287995107, 622588791, 93644108}

{794787, 624486, 893296, 506756, 605900, 289432, 111910, 375079, 157503, 684605, 376542, 955090, 455769}

{999194991, 999164899, 590380, 926813794, 999539242, 999350669, 464802731, 568517252, 999039680, 743841, 128070, 999229611, 999552351}

Returns: 166736876550507
999633

{0, 628939883, 311568921, 890278166, 596695572, 596906228}

{}

{}

Returns: 166601888045728
999890

{0, 753679904, 466914695, 0, 935608930, 586484038}

{487906, 944104, 369556, 3041, 403080, 417223, 836827, 337484, 315127, 317240, 422026, 179640, 78804, 84813, 603628, 790462, 682280, 407649, 509977, 939552, 733308, 282377, 863969, 807935, 381647, 365128, 388666, 775817, 194848, 705481, 830487, 15612, 394472, 97668, 41574, 13757, 428482, 966859, 765270, 813699, 231671, 319735, 253886, 195321, 30621, 619912, 423931, 120978, 843861, 827161, 46111, 710030, 445638, 733430}

{999507302, 999725633, 950852919, 314340, 104070, 813959, 999377189, 999596536, 429525967, 999703118, 485735, 280359950, 762406, 116933604, 999646663, 714698, 63537838, 963901, 105432, 474286, 361812, 999195696, 20078, 999206667, 999413087, 891651, 841911840, 57815089, 95639, 882470, 97836897, 81302161, 547675, 153479, 999045022, 999672193, 999285212, 211669536, 410496412, 542542, 133589, 499896, 70470305, 449350207, 908845, 999598048, 32786, 244494846, 999830388, 868833, 121844, 985065523, 468375942, 924255240}

Returns: 166658164255950
999035

{154864644, 743069424, 59510307, 0, 15686392, 546643221}

{}

{}

Returns: 166649828138093
999264

{0, 765584311, 961461528, 974176340, 772923545, 256454893}

{278674, 184028, 982760, 183935, 864525, 666492, 72347, 388265, 794459, 802896, 320076, 59190, 508237, 678194, 604385, 259279, 331072, 488468, 652452, 707427, 677896, 202195, 58108, 578517, 56861, 664908, 400265, 935377, 190932, 482805, 818523, 687568, 188297, 312259, 113579, 410849, 634749, 425169, 405377, 588740, 135026, 2136, 600028, 752821, 424516, 559180, 734490, 20696, 699908, 893564, 423499, 139152, 52497, 282938, 332168, 596916, 717077, 877283, 570151, 535986, 243416, 104922, 631801, 727348, 860738, 353956, 456250, 360113, 797868, 969532, 662416, 308320, 763867, 161456, 308565, 899638, 954114, 144605}

{999548947, 238691, 999152215, 410767461, 489205, 387158, 999403747, 129634, 999660927, 78786585, 999647317, 287233379, 402340422, 999078486, 763391585, 999273091, 1963, 673841, 516014320, 527795, 979887576, 905546, 999251761, 999674349, 876536874, 875186631, 98219, 242195906, 999358154, 752342, 999619356, 605898, 838673362, 441387, 606571, 892430668, 547185, 999957693, 999632597, 999283763, 50853, 806678639, 61202691, 410785116, 999456923, 911672, 798968, 245076133, 999053738, 309425157, 935380946, 965635, 999782798, 999572698, 999410328, 655235146, 664399726, 999452149, 999867805, 966202836, 257367751, 384129, 209452978, 999390257, 285233, 999571091, 138491946, 833000099, 617822, 105881, 999757163, 776973, 999516865, 225776286, 999623957, 836803986, 999361920, 609827174}

Returns: 166487696139236
999189

{0, 139096533, 614784165, 0, 718934696, 234986388}

{479490, 391438, 934676, 899678, 449327, 193452, 580022, 209726, 916597, 689726, 280955, 616057, 426644, 29863, 341459, 553018, 452929, 72120, 856416, 521515, 131146, 5383, 779968, 197525, 663970, 899176, 176208, 20624, 17887, 736649, 486074, 570072, 162812, 49364, 500645, 657434, 892187, 505150, 124866, 777625, 581353, 872267, 547231, 451313, 484692, 8184, 125298, 693111, 930313, 222912, 529673, 688713, 579938, 875341, 684573, 935325, 573747, 373449, 263333, 678521, 161373, 773152, 143095, 755014, 625696, 980562, 902024, 457186, 172937, 532257, 676835, 45315, 976907, 402065, 76423, 704175, 554909, 526360, 983945, 371750, 283151, 315998, 822098, 456273, 346429, 508969, 172367, 325445}

{475203, 888185925, 999042491, 658788782, 803067265, 615821, 523228, 999388025, 751193148, 999341719, 999973718, 936244, 999640133, 999237882, 999027663, 999247447, 999512934, 658997961, 474211, 55818, 829935822, 830848, 453630, 999705259, 784982, 841038, 999732497, 564859, 570226487, 364000155, 999110474, 302336, 865835, 170914, 680087992, 616171317, 374416330, 825119114, 999431815, 999955873, 166321, 999815253, 999163834, 899243, 999129758, 760086962, 943275702, 958741750, 999698735, 63599, 999128123, 15252, 821494, 999080011, 195876, 307933240, 821916, 999796517, 826827826, 930546718, 92262, 999650989, 999817815, 999224230, 999182582, 615083148, 495163124, 849967, 988645089, 712760990, 999283362, 904409394, 584226, 999029168, 223907019, 999277561, 435179500, 823590727, 829177, 999598838, 999353797, 541912, 999053985, 100260413, 229606742, 518169, 999879742, 901432}

Returns: 166539386655758
999560

{0, 503901028, 905242343, 931857700, 626616409, 535800696}

{}

{}

Returns: 166137205803010
999281

{0, 0, 225802280, 0, 786228390, 166848380}

{}

{}

Returns: 162472758481274
999542

{0, 989937082, 37897674, 254955251, 0, 659553477}

{}

{}

Returns: 166442947492446
8

{0, 0, 47, 0, 0, 42 }

{ }

{ }

Returns: 188
1000000

{123456789, 234567890, 345678901, 456789012, 567890123, 678901234 }

{7 }

{890123456 }

Returns: 166719112255834
10

{0, 0, 0, 0, 0, 0 }

{0, 1, 2, 3, 4, 5, 6, 7, 9, 8 }

{500, 300, 400, 200, 400, 700, 100, 300, 300, 100 }

Returns: 1500
6

{1, 2, 3, 4, 5, 6 }

{0, 1, 2, 3, 4, 5 }

{5, 17, 17, 3, 17, 4 }

Returns: 17
1000000

{123456, 234567, 345678, 456789, 567890, 678901 }

{ }

{ }

Returns: 166802868545204
5

{1, 2, 3, 4, 5, 6 }

{0, 1, 2, 3, 4 }

{3, 3, 1, 2, 0 }

Returns: 1
1000000

{123456789, 234567890, 345678901, 456789012, 567890123, 678901234 }

{ }

{ }

Returns: 166718506325934

Statistics

Problem Statement for "Prominence"

Problem Statement

Definition

Notes

Constraints

Examples