在Mars星球上,每個(gè)Mars人都隨身佩帶著一串能量項(xiàng)鏈。在項(xiàng)鏈上有 N顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子,這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。并且,對(duì)于相鄰的兩顆珠子,前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo) 記。因?yàn)橹挥羞@樣,通過吸盤(吸盤是Mars人吸收能量的一種器官)的作用,這兩顆珠子才能聚合成一顆珠子,同時(shí)釋放出可以被吸盤吸收的能量。如果前一顆 能量珠的頭標(biāo)記為m,尾標(biāo)記為r,后一顆能量珠的頭標(biāo)記為r,尾標(biāo)記為n,則聚合后釋放的能量為m*r*n(Mars單位),新產(chǎn)生的珠子的頭標(biāo)記為m, 尾標(biāo)記為n。
需要時(shí),Mars人就用吸盤夾住相鄰的兩顆珠子,通過聚合得到能量,直到項(xiàng)鏈上只剩下一顆珠子為止。顯然,不同的聚合順序得到的總能量是不同的,請(qǐng)你設(shè)計(jì)一個(gè)聚合順序,使一串項(xiàng)鏈釋放出的總能量最大。
例如:設(shè)N=4,4顆珠子的頭標(biāo)記與尾標(biāo)記依次為(2,3) (3,5) (5,10) (10,2)。我們用記號(hào)◎表示兩顆珠子的聚合操作,(j◎k)表示第j,k兩顆珠子聚合后所釋放的能量。則第4、1兩顆珠子聚合后釋放的能量為:
(4◎1)=10*2*3=60。
這一串項(xiàng)鏈可以得到最優(yōu)值的一個(gè)聚合順序所釋放的總能量為
((4◎1)◎2)◎3)=10*2*3+10*3*5+10*5*10=710。
第一行是一個(gè)正整數(shù)N(4≤N≤100),表示項(xiàng)鏈上珠子的個(gè)數(shù)。第二行 是N個(gè)用空格隔開的正整數(shù),所有的數(shù)均不超過1000。第i個(gè)數(shù)為第i顆珠子的頭標(biāo)記(1≤i≤N),當(dāng)i〈N時(shí),第i顆珠子的尾標(biāo)記應(yīng)該等于第i+1顆 珠子的頭標(biāo)記。第N顆珠子的尾標(biāo)記應(yīng)該等于第1顆珠子的頭標(biāo)記。
至于珠子的順序,你可以這樣確定:將項(xiàng)鏈放到桌面上,不要出現(xiàn)交叉,隨意指定第一顆珠子,然后按順時(shí)針方向確定其他珠子的順序。
只有一行,是一個(gè)正整數(shù)E(E≤2.1*10^9),為一個(gè)最優(yōu)聚合順序所釋放的總能量
4 2 3 5 10
710