Ели е наследила от баба си (Нора) винарска изба. В нея има N бутилки вино, наредени в редица. За простота ще ги номерираме с числата от 1 до N, включително. Техните начални цени са неотрицателни цели числа P₁, P₂, …, P_N.

Колкото повече отлежават бутилките, толкова по-скъпи стават те. Ако бутилка i е отлежала Х години, нейната цена ще бъде X * P_i.

В завещанието си бабата на Ели е поискала всяка година внучка ѝ да продава по една от тях, като избира или най-лявата или най-дясната останала. Каква е максималната сума пари, която Ели може да спечели, ако продава бутилките в най-добрия за нея ред? Считаме, че бутилките са отлежавали 1 година, когато бива продадена първата от тях.

Например ако имаме 4 бутилки с цени {P₁ = 1, P₂ = 4, P₃ = 2, P₄ = 3}, оптималното решение би било да продаде бутилките в реда {1, 4, 3, 2} за печалба 1*1 + 2*3 + 3*2 + 4*4 = 29. На първия ред на стандартния вход ще бъде зададено едно цяло число N – броя бутилки. На втория ред ще бъдат зададени N неотрицателни цели числа P₁, P₂, …, P_N. На единствен ред на стандартния изход изведете едно цяло число – максималната сума, която Ели може да постигне.

• 1 ≤ N ≤ 1,000
• 0 ≤ P_i ≤ 10,000

Примерен Вход	Примерен Изход
4 1 4 2 3	29
11 11 17 44 0 13 42 11 20 5 19 9	1337