You live in a strange country: every city is located on a straight line, with city $i$

located at position $i.$ To improve the governance of your country, you decided to rank your cities:

more high$-$ranked cities can help to govern less high$-$ranking cities. After you assign a unique rank

to every city, each city i governs:

itself,

every city $j$ such that rank$[i]ijrank=[4,2,3,1]rank[1]>$rank$[2]rank[3]>$rank$[2]iiijji=[5,2,4,1][1]=51,2,3[1]+[2]+[3]=11[1]+[3]=91,3,4[4]=105+11+9+10=351n5000[i]{10}^9$irank$[i]$ and there $isno$ city with rank higher than rank$[i]$

between i and $j.$

$In$ other words, $it$ governs all cities $to$ the left and $to$ the right $ofit,$ until $it$ reaches a city with

a higher rank. For example, assume that $we$ have $4$ cities, and you decided $to$ assign ranks $as$

rank$=[4,2,3,1].$ Then:

City $1$ governs all the cities.

City $3$ governs cities $2,3,4$: $it$ doesn't govern city $1$ since rank$[1]>$rank$[2]$;

City $2$ governs only itself: cities $1$ and $3$ have a higher rank; city $2$ doesn't govern city $4$ since

they are separated $by$ city $3,$ and rank$[3]>$rank$[2].$

Similarly, city $4$ only governs itself.

Every city i has a value called importance $i(definedby$ various economic and social factors$).$ When

city i governs city $j,$ the governance $of$ city $j$ increases $by$ importance $i.$ For example, assume that

$in$ the above example importance $=[5,2,4,1].$ Then:

City $1is$ governed only $by$ itself, $so$ its governance $is$ importance $[1]=5.$

City $2is$ governed $by$ cities $1,2,3,so$ its governance $is$ importance $[1]+$ importance $[2]+$

importance $[3]=11$;

City $3is$ governed $by$ cities $1,3,so$ its governance $is$ importance $[1]+$ importance $[3]=9$;

City $4is$ governed $by$ cities $1,3,4,so$ its governance $is$ importance$[1]+$ importance$[3]+$

importance $[4]=10.$

Your goal $isto$ choose the ranks $of$ the cities $so$ that the total governance $is$ maximized. $In$ the

above example, the total governance $is5+11+9+10=35,$ which $is$ optimal.

Please implement the following function:

vector Governance$(const$ vector& importance$)$

The function should return the maximum possible total governance.