TopCoder Statistics - Problem Statement

Problem Statement

A sequence x[0], ..., x[N-1] of integers is called convex if for every 1&lt=i&lt=N-2, x[i-1]+x[i+1]&gt=2*x[i]. For example, sequences 7,3,4,5,7 and 4,2,1,3 are convex, while 4,3,1,2 and 5,7,3 are not. A sequence with one or two elements is always convex.

You are given a int[] a containing N elements. You can perform an operation that chooses an index i and replaces a[i] with a[i]-1. Return the minimum number of operations needed to make the sequence convex.

Definition

Class:: ConvexSequence
Method:: getMinimum
Parameters:: int[]
Returns:: long
Method signature:: long getMinimum(int[] a)
(be sure your method is public)

Constraints

a will contain between 1 and 50 elements, inclusive.
Each element of a will be between 0 and 10^9, inclusive.

Examples

{6,5,1,5,3,3}

Returns: 7

You can change the given sequence into a convex sequence by seven operations: doing the operation on a[1] twice, on a[3] four times and on a[4] once yields a convex sequence 6,3,1,1,2,3.
{3,0,1,4}

Returns: 0

No operation is needed; the sequence is already convex.
{1,1,1,0,2,2,2}

Returns: 5

You can change the sequence into 1,0,0,0,0,1,2 by five operations.
{854159326, 317144183, 781399725, 287076509, 894967145, 882577367, 174517516, 134415519, 274494874, 709819883, 59717133, 732212854, 40551288, 232526958, 811785438, 930853743, 946882902, 321325300, 397702677, 376192501, 599310562, 889156198, 135776890, 882710939, 823196361, 681959076, 318666702, 94469186, 536320456, 116468376, 530320850, 436708006, 903344748, 659080120, 774722507, 967315412, 566063635, 43970906, 497687103, 781266213, 876086123, 366960001, 587364849, 191948103, 172568553, 539762057, 83507466, 71569625, 686305822, 663789601}

Returns: 20178337330
{0,4,4,4,9,9,9}

Returns: 12

The following solution is wrong: "First calculating real convex hull then replace each segment with sequence of the form (a,a+b,a+2b,...,a+kb,a+kb+(b-1),a+kb+2(b-1),...,a+kb+l(b-1))". It gives (0,*,*,4,*,*,9)->(0,1,2,4,5,7,9), which is not convex.
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

Returns: 0
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1000000000,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

Returns: 1000000000
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1000000000}

Returns: 0
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1000000000,0}

Returns: 1000000000
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1000000000,1000000000,0}

Returns: 2000000000
{0,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,0}

Returns: 48000000000
{1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,0}

Returns: 24000000234
{1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,999999999,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

Returns: 47
{504635271,355241311}

Returns: 0
{734511753,741524518,684926006,258684254,690034634,394503095,260560884,218817126,766986200,94072616,346656408,805032105,933424656,860006718,918830855,802721560,432069817,755397189,854969596,104159696,49842648,749402073,571206912,45027840,638969433,797168553,758952051,61522678,194273599,296345274,352219783,422732111}

Returns: 11353415804
{411675432,139421302,606022962,90641273,407681520,628980995,919214993,965235179,947238572,797517893,589699255,342295548,700056717,323320718,412310706,200895238,56986863,315599092,899041327,689761492,294900757,8037993,818083372,756019932,450862944,237103067,733232056}

Returns: 10800209455
{550646820,117164654,602220271,810104495,78773727,652395840,823466747,609365703,619225757,739033644,405507720,880317127,112279524,26062776,744365857,606951104,773011263,316828546,210065622,841270552,667688232,432955928,550132071,710471230,991508689,176855134,395601569,793313871,655528968,88398135}

Returns: 13646724256
{955509588,451583919,661251215,354188024,147545699,956951939,541218979}

Returns: 1028879222
{950413038,915954128,978159648,978072771,920122698,933949552,995967239,929556479,994198136,979772435,946288780,933044396,926826917,917692153,948498657,926830459,910222900,927989402,946582278,988225796,934757455,944420348,979231161,976893512,977381962,917338288,967197553,921885836,939880353}

Returns: 938563799
{958362835,942557847,958021289,993328950,967418878,949451185,912238056,957987127,987492835,969768633,920988952,962486112,963002672,901959536,978153426,942336085,942146415,936332153,912212932,913407388,997031145,968528188,931109963,990030444,920328780,932351369}

Returns: 877608624
{936800962,967578398,926819261,981960283,910695292,958399801,973062809,935559805,967956502,900562353,983842247,921412219,964001803,906086718,962318871,993597584,942619979,949645980,909875737,973524210,918008837,948344689,960990709,928788586,979116723,936731899,956360963,991549708,919618795,900709219,992012758,996794777}

Returns: 1295194317
{902501628,903928472,908899768,959438706,979636600,914640061,982076002,922841429,963728556,996758987,981211949,974629652,936500778,932097795,919678171,947679152,952478116,924237334,910333891,947462386,977644291,963225896,917629844,936982364,952608723,987545265,988823064,987276554,929359657,939020762,914557363,938891288,983376691,918299771,985143132,960023704,986193410,907208372}

Returns: 1650079727
{980078796,970704930,923451764,912383459,997127770,930280574,943051664,939397657,924138504}

Returns: 155753389
{99226232,146125375,218327351,253155159,282778456,594083406,740011638,797526383,827729872,849460452,876937478}

Returns: 954122773
{73598725,88344264,224749045,239088615,322106893,362986270,407984436,409263828,448875815,577995848,580343431,598147894,600959421,724659993,798415629,817324347,839733041,879721241,923771438}

Returns: 973050761
{104029046,182307024,188610869,243290051,261076406,262271286,278852628,325752653,373187573,447828273,553343794,565525242,614938967,624551399,711905493,735148761,746200696,750191556,764446655,769135653,803703687,858029268,957298907,964610654,977668988,992465570}

Returns: 1291161451
{10563835,42250409,87703183,88641497,116788149,209535721,218699421,234915478,240428934,248133758,336189417,357749090,377736905,401341071,448738711,475341383,484936116,518531896,534788269,544230888,553504435,555887356,595137466,647102709,734900835,791969790,815480682,839902828,854702561,935539738,941653742,956838089}

Returns: 1209023535
{145208320,233173341,252783028,287981418,303622455,566150703,661361082,695780566,883408045,980973701}

Returns: 373831303
{23785122,30367152,230182052,256365284,270651936,286880705,287067984,342423069,461905080,569567593,570059043,602985978,613108545,616686395,697708852,706859638,707525356,721893502,749194290,775999897,820991663,922665330,925587192,972735228,993829817}

Returns: 1939265409
{52885456,84172016,89877751,94435995,139084838,148969962,195379130,202741644,205275410,307833799,310657426,315606925,316461446,319735085,335678783,337274551,377881898,387725144,457042983,460215560,540454710,544268405,545799925,573917539,583181020,633519224,673302615,689150827,706137358,744984292,766549795,771894162,777819664,788315644,814509875,880641311,907205077,915974780,918591071,931486192,959837046,972771294,991506442}

Returns: 1498769343
{19904775,33169711,82005557,199938468,215633456,245708568,248276882,274947913,310037298,351081701,410600080,433487345,443968561,479524841,575582648,654449601,675008990,678597947,685213982,701049199,729930800,750154383,755159100,813063816,857143120,881201385,978354543}

Returns: 1295756580
{29078945,57098969,71404496,157282970,202955407,364594526,404450012,405922332,413714230,417696073,488648646,491610723,492040390,652761917,705600506,709495142,796324367,817788467,865338091,946893448}

Returns: 1106754394
{220277538,302334240,314042514,375132478,641669098}

Returns: 35174214
{29410847,61037621,70761350,71963812,114737972,127136085,166564682,220106503,246915439,254529549,325778940,349755021,409350531,419748095,534455420,589518424,598411251,684831660,698423388,724779452,736793270,791996926,804052968,840885250,861505748,868504529,931016444,933008227}

Returns: 1182436747
{7543552,77272509,112251117,134888869,159671644,197112344,202878917,226179660,293104284,319667539,320721786,359069414,369614373,373879110,399462318,471389330,479719326,584105923,586776832,596391550,604681560,640536561,672452274,701933419,729106084,766979769,770212048,801526237,828009581,829198364,845562576,877100293,889936770,915996471,931003960,938487338,940283750,951529401,996112658}

Returns: 2683850781
{137020166,177986283,323205796,520185508,625047323,668400050,881242931,948221638,972192782}

Returns: 515766056
{71688148,94958810,122300502,136344160,229541923,246223645,352129997,357119036,421332920,491120730,575409483,609226939,654107027,726901503,730970220,817340883,886023360,898413921,963320709,977936223}

Returns: 611306435
{29719127,39815422,50738087,53794452,61045932,67374610,91380893,121828095,135154856,157493371,175431899,199257045,234155476,261576549,263149920,315702200,338388501,403313414,428153291,438742894,478953886,545273909,561951119,566043627,576877200,608752101,614754723,673164033,691232332,701716548,710928854,790979060,804953985,818902731,819697783,858216952,924602308,967110333,974801365}

Returns: 908992543
{66202018,89324899,117987641,139584080,151889501,182034483,206960080,218948046,293180636,298916496,308690725,318303716,320724140,333321425,357285820,377684449,419504408,450142361,459371042,506998862,520358847,640930266,721923936,724384880,747731937,748270448,773916226,818520866,824767881,828061182,855581640,868293447,870295846,890518857,894790662,915136633,934371576,997448829}

Returns: 1610126697
{7936298,15951576,32108144,36966633,37406734,69762900,207461333,222936614,227531372,276155395,293102780,298010148,319284774,387430044,411956242,471051644,472101117,614164910,619605918,635768154,672055944,685421935,762307857,839603605,844276811,874398056,904867647,944297541,988526031}

Returns: 836129635
{84593657,98303663,137528936,154861352,167778743,179763293,299580391,338527753,374375624,378967736,393382863,409712119,413083517,443560821,473596549,521548253,530427927,538774859,540383964,556765209,655952861,674797265,700257304,745631891,781211201,802257774,824224008,846799831,870218561,948406600,949182987,978062548}

Returns: 1284061273
{66090285,74795494,91913036,129980833,171832352,283110139,354227817,416513721,428859980,460621044,493908079,543501576,546011197,641084397,656751537,680511948,686839349,687151282,704694071,720951922}

Returns: 1382679693
{21340275,53158019,59768959,78529154,83045676,100025092,142789434,167368937,195273602,195306909,248730071,254274631,277240205,343105787,343643371,350696137,436138086,457171179,488409068,540288966,571460390,575848442,597176389,611282678,620984577,625414267,632844154,710042975,749244780,768203853,773767984,793893629,836402493,840489226,841683473,872563498,884399282,888714927,912991287,960899062,964396621,992328742}

Returns: 1537456122
{969651784,911509122,908739753,878449111,869606993,831661368,783648623,774675541,766142041,764806869,710911023,690992239,685245035,667580999,666682054,665360520,659676949,638749184,620158925,599597912,570152955,566081629,484688123,411805282,349849630,349580184,347510140,343841262,326709243,323083104,318329171,296571287,271013064,257511510,253927790,250610006,243188085,223712709,214265665,206054022,192914373,101516139,58649897,42757951,41793279,29264513}

Returns: 2460587705
{820214145,800599656,595912923,562738757,478517411,460216876,382208886,349720492,321399691,290585875,220382157}

Returns: 205732935
{825335042,231589116}

Returns: 0
{937683195,737749056,729302322,695089573,596847921,581354959,388473855,289440197,256133597,159259483,157470209,73321610,61176384}

Returns: 496058920
{746121915,330796430,279932811,279747552,151613250,149384642,126107952,26424503}

Returns: 174725526
{935828343,926701075,836932675,779334371,771896283,717274328,651367257,645518343,604595244,545415519,480506585,442376137,321886068,153449464,118200901,104270376,15960659}

Returns: 1241198216
{896719460,896498693,836968640,787971802,656465284,584588137,563362550,420685261,416612523,367196572,302798774,201673997,127056937,98948137,59516424,57320403,47178676}

Returns: 576072731
{963791772,945356737,928285375,921882625,914436143,876166718,807753724,805740884,785879210,781773565,770369369,767555663,749738274,711342486,706891447,615759188,609965018,592196007,575059277,564361049,434653005,384535003,322784211,238862157,218132849,163862295,53871883}

Returns: 3472546644
{916664803,909658462,478895979,300561617,246964099}

Returns: 211878071
{352967681,197824951,6063649}

Returns: 18309286
{915014741,894099691,828483752,825757937,816439593,763675587,646590792,635309205,566512717,550122940,513841575,505255009,492804076,452510650,366997571,262655049,259609169,256682817,251517254,241533379,231510287,206287373,164998356,96450730,85267107,48537230,31168193,22275588,12116101}

Returns: 1064937771
{973056493,942496483,936102047,926779185,905831463,863869740,863225610,800403127,793574177,782114410,756193841,748998325,745488109,681041421,679689698,657537329,552184823,547300770,480089634,437201688,363265703,277417636,272039301,264853100,238861700,204685026,170611861,67824066,2155825}

Returns: 2794314028
{999555064,961440379,944625521,924542426,907650119,856451333,846434223,835456555,737526283,714016721,712577935,698386651,658544415,652001907,626806131,624403609,610066397,605224347,604850537,591048114,545605673,537778625,481219435,478242254,476185372,472467130,465619206,456368257,450493972,415849089,409998915,407897570,372665156,352151905,351385142,338901367,281531524,273684313,257188510,252267667,112463044,109024945,95580249,93681815,89296753,61018537,48959642,37276661}

Returns: 2330817775
{913710957,892092526,889032106,868550913,867748872,863752661,837062737,812332214,807429494,733317300,727935781,669229316,607818282,597842097,575279103,519126504,501237853,468026529,441144775,438207089,364578709,342255235,322432018,301839309,300900678,289234827,239026701,219267262,210685202,203307938,201730945,165006938,94022258,87767132,54845295,51717065,48930895,3541651}

Returns: 1302390484
{913764061,911354108,899656090,812384015,595070523,542310431,459130793,373391463,359907765,292157257,182068635,147552236,100788626,46633469}

Returns: 509365260
{931547787,919926225,886536759,788042763,763571024,753693133,732031043,724627952,710351358,679536972,678539395,652349941,631991754,623823065,591140945,585221798,518851367,503494815,469102298,407877425,404226365,358824465,331149043,324081283,314237295,303168567,299462301,297801965,286384552,275435734,267891684,262192188,248572990,246123007,241803814,200252897,179529510,178112450,169655291,163411231,135769553,99500649,81778480,36883999,8230347}

Returns: 1856001899
{881737148,803626801,586963197,506525252,445742784,432618806,367790307,358417021,318612795,286561432,194984327,82299154}

Returns: 444135509
{974512519,913860425,911423780,850254343,681000931,507092340,475301753,469239172,449711197,381593589,344926211,333521896,261930675,239238011,216092917,147361458,96493808}

Returns: 694315914
{977773083,914890791,886828031,869990896,840609500,838564855,823240206,774798809,771387264,768254400,762870399,730702258,704517648,697482935,578925730,572875271,530000408,528689262,413144454,403916568,329922428,129462142,107061148,64781481,46577601,37686762,25561676}

Returns: 2916924969
{993437429,970094392,963899797,935254268,922431896,891915163,884742144,858692049,850601304,772381625,741994881,737309304,733900102,716341488,703053496,640238632,634366707,631417838,624681256,603715507,600323881,568808201,565677621,535280059,519330777,445565371,423549791,270480585,264852141,234828979,232899714,193867745,172674353,170790157,150953386,114300733,71685154}

Returns: 2211137715
{4950,4800,4747,4356,4040,3762,3737,3663,3600,3465,3465,3366,3232,3168,3131,3131,2700,2574,2200,1919,1881,1881,1700,1616,1600,1515,1515,1500,1500,1300,1287,1000,900,792,707,700,297,198,99,0}

Returns: 8817
{4949,4752,4545,4455,4356,4059,4000,3663,3600,3535,3465,2800,2772,2700,2673,2626,2424,2400,2376,2323,2323,1980,1919,1900,1900,1818,1717,1700,1414,1287,1000,900,600,505,495,200,198,100}

Returns: 9126
{4554,4400,4158,3939,2871,2828,2800,2727,2574,2500,2424,1717,1100,200}

Returns: 7754
{5050,4646,3939,3800,2828,2828,2475,1089,800,300,200}

Returns: 2208
{4700,4400,4400,4300,4257,4242,4100,3861,3737,3636,3100,2900,2673,1919,1919,1900,1616,1188,1089,707,693,396,396,303}

Returns: 7801
{4949,4851,4747,4300,3861,3838,3400,3300,3200,3168,3100,2970,2871,2828,2772,2100,2079,2000,2000,1584,1400,1300,1188,1111,1089,700,700,594,505,495,495,300,200,101,99}

Returns: 4750
{5000,5000,5000,4950,4900,4848,4752,4653,4545,4500,4444,4257,4158,4158,4100,4040,3900,3838,3737,3564,3564,3434,3333,3232,3200,3200,3168,3000,2970,2900,2525,2500,2475,2400,2277,2178,1818,1515,1313,1212,1188,891,808,500,101,0}

Returns: 29491
{4950,4752,4646,4554,4500,4444,4400,4343,4200,4200,4158,3762,3663,3600,3333,3267,3168,3030,2424,2200,1818,1800,1700,1400,1212,404,396,303,100}

Returns: 16764
{4950,4848,4700,4646,4300,4242,4141,4000,3663,3434,3366,3200,3168,3131,3000,2970,2828,2772,2727,2626,2525,2121,2079,2079,1515,1485,1386,1300,693,594}

Returns: 8184
{5050,5000,4800,4752,4700,4653,4545,4400,4158,4100,3762,3636,3600,3232,3100,3069,2929,2900,2828,2323,1515,1400,1287,1111,594,594,495,303,0}

Returns: 13461
{5000,4950,4554,4242,3838,3700,3333,3300,2574,1683,808,400,297}

Returns: 6046
{4851,4848,4700,4257,4059,4059,4040,3800,3600,3535,3400,3333,3200,3100,3030,2970,2900,2871,2871,2800,2475,2300,2200,2000,1980,1900,1717,1717,1616,1616,1616,1485,1313,1000,900,606,600,404,200,99,0,0}

Returns: 7307
{4900,4646,4141,4000,3861,3762,3737,3600,3333,3131,2900,2871,2800,2772,2727,2727,2700,2500,2300,2200,2020,1717,1700,1700,1485,1386,1200,990,909,707,707,505,505,505,495,396,200,101,99,0,0}

Returns: 5935
{3800,2600}

Returns: 0
{4851,4257,4059,3737,3564,3400,3267,3131,3000,3000,2323,2020,1980,1919,1313,297,101}

Returns: 7124
{4747,4700,4646,4554,3737,3600,3500,3400,2400,2200,1800,1683}

Returns: 3286
{4900,4900,4554,4400,4158,4000,3939,3939,3939,3762,3737,3700,3636,3030,2871,2727,2600,2574,2400,2020,1919,1818,1717,1414,1111,1089,1010,990,990,909,792,700,600,594,404,300}

Returns: 7056
{4950,4949,4848,4752,4653,4653,4600,4545,4444,4400,4356,4242,4200,4141,4040,4000,4000,3960,3861,3800,3663,3000,3000,2929,2929,2828,2600,2200,2000,2000,1881,1800,1600,1500,1212,1188,1111,1010,990,808,808,693,600,505,303,303,297,202,202}

Returns: 15729
{4752,4646,4545,4500,4455,4300,4158,4158,3861,3737,3663,3600,3564,3500,3300,3100,3000,2772,2673,2574,2400,2400,2323,2277,2222,2121,1782,1616,1485,1414,1300,1287,1212,990,693,404,101,0}

Returns: 11206
{4949,4900,4600,4545,4141,4100,4100,4059,4000,3838,3762,3600,3465,3465,3434,3267,3168,3030,3030,3000,2828,2525,2525,2475,2424,2323,2323,2121,2100,1616,1515,1386,1300,1287,1287,1100,1010,800,707,693,505,505,404,400,297,198,100,99,0}

Returns: 7634
{0,0,0,100,101,202,300,400,404,495,505,707,800,1313,1414,1500,1919,1980,2121,2222,2376,2500,2600,2600,2828,2828,2900,2929,3267,3838,3939,4059,4100,4100,4257,4300,4343,4356,4400,4455,4747,4800}

Returns: 11585
{100,2000,3232,4554,4949}

Returns: 2214
{0,0,100,297,300,404,594,606,792,891,900,990,1100,1212,1500,1500,1584,1600,1683,1980,2300,2400,2400,2424,2574,2727,2727,3030,3168,3465,3465,3500,3700,3861,3939,4059,4141,4200,4257,4343,4356,4400,4500,4500,4545,4747,4848,5000}

Returns: 9547
{100,495,606,707,909,990,1500,1584,1683,1700,1818,1919,2020,2222,2772,2900,3267,3636,3737,3939,4100,4158,4400,4500,4545,4554}

Returns: 6989
{200,303,404,808,1111,1287,1287,1386,1485,1584,1800,1818,2020,2200,2222,2376,2400,2500,2600,3000,3267,3535,4242,4554,4554,4600,4851,4949,4949}

Returns: 7365
{0,396,505,505,594,606,808,891,1089,1212,1287,1386,1900,2000,2079,2200,2525,2574,2673,2772,2871,2970,3069,3069,3168,3200,3366,3366,3465,3600,3663,4141,4343,4500,4500}

Returns: 7906
{0,0,101,101,198,198,303,693,891,909,909,1100,1414,1515,1584,2200,2222,2323,2600,2727,3000,3131,3400,3465,3636,4059,4444,4500,4848,4851,4851}

Returns: 4236
{101,404,693,707,1010,1111,1683,1700,1818,1881,2020,2300,2626,2800,3400,3400,3838,4000,4040,4242,4444,4455,5050}

Returns: 4196
{0,202,202,303,404,505,693,707,707,1010,1188,1300,1313,1616,1683,1900,2020,2200,2277,2300,2376,2424,2673,2673,2800,2828,2929,2970,3100,3168,3500,3900,4100,4455,4851,4851,4900,5050}

Returns: 7213
{100,300,303,693,792,1300,1683,1782,1818,1980,2178,2323,2424,2500,2574,2700,2929,2929,3200,3838,4040,4200,4356,4444,4600,4600,4646}

Returns: 8143
{99,1616,1818,3069,3200,4752}

Returns: 1556
{99,99,100,100,594,600,707,900,990,1300,1386,1515,1584,1600,1683,1717,1980,2020,2121,2222,2300,2323,2376,2400,2727,3069,3100,3100,3663,3700,3800,3861,3939,4158}

Returns: 7833
{200,594,693,1010,1111,1500,1683,1700,2121,2376,2500,3000,3267,3366,3366,3762,4158,4158,4257,4257,4356,4646,4848,4848}

Returns: 7222
{100,202,297,303,396,500,900,1111,1414,1584,1616,1782,1782,1818,2000,2020,2100,2200,2277,2323,2800,2871,3465,3500,3600,4158,4158,4200,4200,4300,4343,4400,4455,4545,4554,4747,4800}

Returns: 11710
{100,101,1100,1188,1584,1600,1919,1980,2222,2376,2424,2525,2871,3069,3100,3366,3535,3960,4100,4900,4950}

Returns: 6397
{1000,1188,1818,2376,2424,4800}

Returns: 582
{101,303,404,505,891,1010,1089,1111,1111,1485,1881,2121,2277,2772,2929,3300,3838,4343,4545,4545}

Returns: 2745
{0,198,200,202,594,600,693,693,700,700,1010,1300,1313,1485,1485,1485,1600,1782,1818,2000,2100,2178,2277,2323,2626,2727,2828,2929,3000,3030,3535,3564,3737,3838,3900,4059,4100,4141,4141,4400,4444,4545,4554,4600,4646,4646,4747}

Returns: 11483
{303,495,1287,1287,1600,2121,2525,2800,2970,3200,3232,3465,3663,4059}

Returns: 3697
{200,1000,1000,1414,2475,2500,3564,3800,3900,4040}

Returns: 3008
{1,2,2,4,6,7,8,9,12,13,16,19,19,23,23,24,26,28,30,32,33,34,38,39,40,41,41,42,43,44,44,45,46,47,47,48}

Returns: 254
{1,1,7,8,9,9,13,14,17,17,17,19,19,19,21,23,24,26,26,28,28,29,30,31,32,32,33,33,34,35,36,36,37,39,39,40,43,43,43,44,46,50}

Returns: 239
{3,3,6,10,10,12,15,18,24,29,31,32,33,34,37,37,46,47,49,49}

Returns: 68
{9,10,11,14,15,16,37}

Returns: 3
{1,3,6,10,12,12,15,17,18,20,21,21,22,24,29,33,37,39,48,49,50}

Returns: 60
{1,3,9,13,14,18,19,22,24,24,25,25,27,28,28,28,36,42}

Returns: 95
{1,2,5,8,10,12,13,13,18,19,19,20,21,23,23,24,27,28,30,32,39,39,40,41,41,41,42,42,43,45,48,49}

Returns: 177
{3,6,8,8,8,10,12,12,18,19,22,23,24,25,27,29,30,32,35,41,41,42,49,50}

Returns: 42
{1,4,4,5,6,9,11,14,16,22,26,27,29,35,37,39,41,41,47}

Returns: 46
{1,3,6,8,8,14,16,16,17,18,23,23,25,26,27,29,32,32,33,34,35,38,40,46,47}

Returns: 94
{900000007,450000068,450000027,450000028,450000035,450000023,450000034,900000061,900000100,900000003,900000023,900000064,31,900000020,450000082,450000031,450000077,900000029,450000059,450000047,900000025,6,900000018,450000073,25,73,900000043}

Returns: 10800000205
{450000036,900000057,66,32,450000049}

Returns: 675000006
{450000096,98,28,38,900000092,450000032,900000036,89,11,450000041,36,450000047,450000019,900000081,900000075,35,54,450000082,450000017,450000061,7,99,450000078}

Returns: 6750000657
{72}

Returns: 0
{6,450000014,900000051,450000039,12,900000060,900000042,450000098,17,450000070,450000002,450000000,900000040,60,13,900000046,450000070,900000087,450000001,900000088,450000073,900000039,450000014,450000001,80,900000072,450000084,450000091,900000021,900000077,900000077,450000008,450000027,900000097,900000059,33,67,900000049,53,900000093,900000091,450000043,900000065,7,450000088,900000082}

Returns: 23400001916
{450000066,900000037,900000094,450000026,54,450000047,20,450000059,450000096,900000034,93,36,7,96,900000013,73,27}

Returns: 4725000371
{42,900000008,450000023,52,900000070,450000031,900000054,17,900000098,900000027,5,450000032,56,900000070,450000066,900000077,62,900000008,450000052,900000095,31,31,77,24,900000058,450000089,900000038,900000091,75,450000067,900000065,69,900000039,10,13,900000061,47,900000012,900000059,450000059}

Returns: 18000001327
{10,46,6,900000081,900000064,900000095,900000076,900000032,71,900000045,450000043,43,900000064,44,450000067,87,450000017,900000028,86,450000064,450000033,450000086,900000027,450000081,900000013,450000053,450000002,450000030,450000098,69,74,450000007,450000054,42,450000039,900000024,450000041,900000086,32,450000006,100,450000059,900000096,900000051,450000061,900000093}

Returns: 19575001275
{450000088,1,25,450000015,53,38,450000054,450000025,21,450000063,450000018,900000031,900000098,450000003,450000060,53,98,450000040,77,900000020}

Returns: 5400000212
{94,900000026,450000088,900000021,900000033,19,900000065,900000011,80,450000014,450000098,450000055,900000046,900000013,85,450000045,37,450000090,900000071,900000019}

Returns: 9000000293
{1,31,45,50,59,60,66,97,450000022,450000070,450000081,450000083,450000084,900000000,900000010,900000014,900000015,900000037,900000038,900000043,900000049,900000074,900000100}

Returns: 4049999339
{72,900000072}

Returns: 0
{11,21,24,32,41,61,81,91,98,450000015,450000020,450000030,450000041,450000043,450000051,450000057,450000059,450000061,450000065,450000073,450000073,450000076,450000076,450000082,450000089,450000095,450000097,900000009,900000023,900000032,900000034,900000043,900000051,900000057,900000060,900000061,900000075,900000075,900000091}

Returns: 6299998891
{4,31,54,450000015,450000017,450000025,450000047,900000005,900000015,900000026,900000060}

Returns: 1349999796
{6,9,17,31,52,71,88,89,96,450000001,450000001,450000002,450000011,450000019,450000047,450000051,450000059,450000065,450000073,450000077,450000082,450000093,900000012,900000015,900000034,900000047,900000052,900000067,900000068,900000075,900000077,900000081,900000084,900000094}

Returns: 5174999014
{7,7,8,10,13,14,25,33,46,47,58,59,61,77,450000010,450000012,450000021,450000022,450000035,450000057,450000064,450000069,450000077,450000086,450000088,900000007,900000010,900000012,900000015,900000015,900000036,900000040,900000050,900000057,900000061,900000069,900000077,900000078,900000085,900000089,900000095}

Returns: 6749999055
{1,6,16,28,36,44,66,73,74,84,88,90,450000000,450000006,450000012,450000015,450000035,450000040,450000047,450000054,450000067,450000071,450000072,450000076,450000082,450000083,450000086,450000088,450000100,900000004,900000009,900000011,900000020,900000028,900000042,900000051,900000055,900000056,900000061,900000073,900000077,900000079,900000090,900000091}

Returns: 6749998770
{24,28,36,47,73,450000008,450000009,450000010,450000014,450000015,450000025,450000027,450000032,450000036,450000047,450000057,450000058,450000069,450000077,450000077,450000078,450000079,900000001,900000003,900000005,900000013,900000027,900000032,900000049,900000050,900000064,900000079,900000084,900000084,900000093,900000096,900000100}

Returns: 6749998912
{0,35,36,51,58,60,65,78,100,450000002,450000011,450000013,450000014,450000020,450000030,450000043,450000059,450000087,450000094,450000094,450000095,450000097,450000098,450000099,450000100,900000009,900000020,900000038,900000039,900000041,900000044,900000049,900000061,900000072,900000075,900000078,900000088}

Returns: 5849998928
{12,12,13,21,38,80,450000065,450000065,450000086,900000024,900000033,900000052,900000084,900000084}

Returns: 1799999843
{80,47,24}

Returns: 0
{900000098,900000096,900000088,900000085,900000085,900000081,900000077,900000060,900000051,900000048,900000026,900000006,450000096,450000086,450000082,450000079,450000051,450000021,450000018,450000012,94,94,92,79,69,33,9}

Returns: 4949999468
{900000082,900000052,900000050,900000048,900000048,900000026,900000015,450000095,450000089,450000065,450000037,450000034,450000024,450000019,450000016,84,67,61,59,57,51,4}

Returns: 2924999468
{900000095,900000090,900000084,900000083,900000082,900000076,900000062,900000052,900000051,900000039,900000037,900000035,900000031,900000021,900000021,450000086,450000084,450000066,450000062,450000058,450000055,450000049,450000041,450000038,450000011,450000007,95,93,84,72,70,69,67,63,59,51,36,26,9}

Returns: 6299999154
{900000078,900000078,900000070,900000054,900000050,900000015,450000089,450000085,450000080,450000074,450000071,450000067,450000063,450000063,450000062,450000061,450000049,450000034,450000032,450000031,450000018,450000013,450000008,450000002,99,92,89,79,77,68,66,64,29,19,8}

Returns: 4949999213
{900000094,900000035,900000034,900000012,900000002,900000002,450000099,450000095,450000093,450000092,450000088,450000083,450000083,450000081,450000066,450000064,450000055,450000038,450000035,450000013,450000009,450000001,81,79,69,67,55,30,29,19,19,11}

Returns: 4499999224
{900000063,900000059,900000049,900000048,900000038,900000036,900000030,900000026,900000025,900000015,900000015,900000007,450000091,450000087,450000062,450000055,450000046,450000028,450000028,450000021,450000015,80,77,34,31,30}

Returns: 4949999381
{900000088,900000088,900000077,900000067,900000053,900000039,900000038,900000028,900000026,900000017,900000017,900000013,900000012,450000095,450000057,450000053,450000042,450000009,450000002,82,52,47,38,34,29,19,14,12,12,0}

Returns: 5399999265
{900000081,900000069,900000038,900000030,900000029,450000087,450000073,450000063,450000027,450000022,450000022,450000010,450000008,94,73,33,27,18,14,12,10}

Returns: 2474999439
{900000094,900000090,900000082,900000077,900000065,900000049,900000039,450000086,450000079,450000071,450000065,450000064,450000062,450000024,450000012,100,77,59,56,52}

Returns: 2924999601
{48700039,189915098,389600050,183296679,91935056}

Returns: 551859186
{334490080,318288744,192285080,411125070,26025086,243815085,375485038,68823854,164465011,16960075,293495093,33965030,118305040,299289933,24260072,395719179,46064241,404510926,143845063,210995098,462615089,97715050,113020097,71965022,232880030,130630100,59880052,292133497,67723608,488027682,225675068,375765154,17890063,379445919,13007662,264105003,86545007,337842632,395079013,382866645,350660010,166315063,406136259,60707153,330170026,191600037,307040011,240733141}

Returns: 8245088170
{107876636,258191675,463602719,472004385,320699134,492143416,193518780,425255027}

Returns: 1253152793
{324555021,48210035,186067225,246025031,322054439,30071031,420224071,439705095,440488109,218580093,61852380,489530097,276795433,424235088,270964244,281155056,340453135,169630013,260072075}

Returns: 3360561523
{498684817,55426100,328960042,468398695,460502120,325140042}

Returns: 687011646
{107091497,169985015,217485031,219508985,201840040,152195005,199990090,314465026,413967790,361762369,296820070,112745061,247959630,455596142,412025080,245809176,174990066}

Returns: 2234756419
{229535061,424680068,136947454,288872804,37517549,200685185,286550009,103750807,345895015,99210069,123279744,192635018,428920016,368190019,137825053,302910002,320245029,248824791,386042193,49064892,490520100,180056056,184110092,36357363,242210057,127085426}

Returns: 4394250000
{18175091,159876984,434585042,353090043,417208513,74900067,48059651,435065041,240158064,185572118,141023232,276520326,443748775,94183843,14728008,289485057,195605040,354360002,290598117,278100082,366178275,351650334,412317451,331341300,387445047,13652830,258156628,233960056,370179035,276435375,254990010,427325075,159400037,116848456,102255047,334910090,268750000,72569513,135122030}

Returns: 8534285042
{152815609,142340098,429730042,335875092,387972645,242783581,429585089,447535000,110972278,101280290,275875030,197965075,260557120,48600036,119689013,479150065,149559906,418795004,194640098,62767644,116918395,160792205,84651988,300260096,378010635,80970002,152675553,245719187,62815028,482116416,126755359,183260100}

Returns: 4721986094
{437007397,190120076,55300056,301670085,61037269,76165233,23059673,116395057,148079661,297880034,216633352,296504313,173710038,468455052,184555067,407596536,185955059,114200031,325775187,90345047,210192039,330871173,454905037,94425076,274219855,219825044,45119096,241953385,490438097,101835400,78370094,31046216,472994586,347185053,113865054,202620094,422069491,306295088,456445037,234366867,282360041,494198866}

Returns: 6632829740
{5}

Returns: 0
{429611683,52252704,96858989,166280803,187733375,389385981,463046239,271687133,315515607,334573373,412492836,179677959,195124180,228992228,129201987,249259589,300836688,108272543,176958283,329622267,348514348,250731185,380588772,138839020,381668490,167137385,363033048,401871125,456260667,60342735,54181858,447792106,113631540,227173996,30411111,317957933,314151579,217092925,311720865,279074454,392476302,167519967,269409935,95122407,11089468}

Returns: 9392038429
{380364608,509496039,176360856,395855998,25888171,166418297,362446479,235816702,491548447,225360885,114150795,47950041,170644626,133457562,84654671,328847042,505505029,87588082,131326511,87191563,379814274,197332126,190994016,467420412,47154705,128456529,109494373,274778253,395792854,388482523,74923549,343848783,210362986,338999222,93366911,337258866,467720544,216401675,145208373,231790954,359844300,390541541,177459501,478906095,29953047,193222923,32462536,188312900,35010980,4738871}

Returns: 9950292601
{11046917,105952251,87489988,174196467,93805441,148982428,241700508,311563408,235857568,180277926,167825581,152464991,142880115,199077171,168707055,319641718,223837777,188512886,190127639,15767552,11282219,254162360,138864881,265321455,247142186,115813366,96552169,100000808,14002015,230232219,230963719,35710384,86351216,287635735,266186752,110535392,92073797,124692002,202673305,112908950,328193389,211115861,183200879,143456222,146384878,292206040,306406237,17395394,292424634,339022}

Returns: 8019294697
{1361955, 207579012, 628145516, 376140462, 883515280, 186969585, 762888635, 326402539, 98152102, 158176572, 61402892, 127860889, 9580638, 570870044, 646139319, 178509022, 484027666, 61263304, 841082555, 558212774, 940563715, 26389629, 579113528, 496147999, 925801172, 837151740, 70301173, 656585275, 285845005, 902071050, 403573723, 727123762, 9467290, 296231662, 631265400, 899374333, 520690249, 798571510, 491747709, 799313372, 643215695, 789204466, 614608448, 162733264, 456517316, 555253431, 806956091, 181457954, 528156706, 751354013 }

Returns: 21040690366
{1, 1, 1, 0, 2, 2, 2 }

Returns: 5
{240161884, 223346407, 206530931, 189715455, 172899979, 156084503, 139269027, 122453551, 105638075, 88822599, 72007123, 55191647, 256539289, 457886932, 588887396, 719887861, 850888326, 981888791, 847675519, 713462248, 651607690, 589753132, 527898574, 403734060, 279569546, 274449079, 269328612, 264208145, 259087678, 253967211, 248846744, 243726277, 238605810, 233485343, 228364876, 223244409, 218123942, 213003475, 207883008, 202762541, 197642074, 192521607, 187401140, 182280673, 177160206, 172039739, 499034107, 826028476, 466038118, 106047761 }

Returns: 11365983726
{772661395, 705084821, 888450278, 414333100 }

Returns: 406540604
{1, 5, 4 }

Returns: 3
{194651380, 27581100, 37476435, 233093616, 774641266, 273261369, 971074917, 866999265, 246716319, 975586225, 363233711, 72001065, 25574493, 527060239, 804256114, 364453817, 515343111, 842621173, 971657600, 968231217, 804419916, 798874770, 378310174, 307099796, 29611553, 350416321, 556989186, 509277978, 213554715, 944851678, 278764980, 108781125, 536632373, 866919120, 825533767, 27567282, 943073614, 182153109, 41083222, 353162890, 700652490, 21819213, 870440562, 388360987, 34377764, 53389384, 363851405, 942749646, 236791667, 114615237 }

Returns: 21137548456
{1, 1000000, 1 }

Returns: 999999
{854159326, 317144183, 781399725, 287076509, 894967145, 882577367, 174517516, 134415519, 274494874, 709819883, 59717133, 732212854, 40551288, 232526958, 811785438, 930853743, 946882902, 321325300, 397702677, 376192501, 599310562, 889156198, 135776890, 882710939, 823196361, 681959076, 318666702, 94469186, 536320456, 116468376, 530320850, 436708006, 903344748, 659080120, 774722507, 967315412, 566063635, 43970906, 497687103, 781266213, 876086123, 366960001, 587364849, 191948103, 172568553, 539762057, 83507466, 71569625, 686305822, 663789601 }

Returns: 20178337330
{1, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

Returns: 24000000198
{100644807, 208824616, 965402955, 450617412, 681295279, 67915640, 684078665, 773498128, 670693140, 21122360 }

Returns: 4015257177
{9, 8, 7, 6, 6, 4 }

Returns: 1
{239313357, 440048504, 588558884, 338663599, 408456151, 396655486, 2788683, 22944598, 467861995, 345837908, 44234513, 382369865, 46930527, 160493858, 271817716, 279621058, 527049522, 442974087, 847227192, 816031730, 467297001, 873039797, 927727688, 500698241, 118364707, 911064484, 831614069, 82306379, 582624695, 272124758, 242280810, 406974616, 491348526, 257352374, 401183052, 258958824, 443965436, 569416650, 804553674, 779313232, 995036094, 886411574, 716422494, 624342624, 951791508, 110484543, 82622902, 394149547, 367668179, 353784150 }

Returns: 19389104910
{854159326, 317144183, 781399725, 287076509, 894967145, 882577367, 174517516, 134415519, 274494874, 709819883, 59717133, 0, 40551288, 232526958, 811785438, 930853743, 946882902, 321325300, 397702677, 376192501, 599310562, 889156198, 135776890, 882710939, 823196361, 681959076, 318666702, 94469186, 536320456, 0, 530320850, 436708006, 903344748, 659080120, 774722507, 967315412, 566063635, 43970906, 497687103, 781266213, 876086123, 366960001, 587364849, 191948103, 172568553, 539762057, 83507466, 71569625, 686305822, 663789601 }

Returns: 20480185116

Statistics

Problem Statement for "ConvexSequence"

Problem Statement

Definition

Constraints

Examples