We have an array of length N

The array consists of balloons each with some points A_{i}

Initially our score is zero .

Whenever we shoot a balloon A_{i} , product of A_{i-1} and A_{i+1} gets added to the total score and the balloon A_{i} is removed from the array to form a new contiguous sequence.

If a balloon has only right of only a left neighbor, the value of that neighboring balloon is added to

the total score.

At the end when there is only one balloon left , its score is added to the total

We can choose any balloon during this process.

**The goal is to maximize the score .**

**Sample test cases :**

**TC 1:**

N=4

Arr= 1 2 3 4

way to get maximum score = 3->2->1->4 ( order in which balloons are shot)

Maximum score =20

**TC 2:**

N=5

Arr= 3 10 1 2 5

way to get maximum score = 3->1->2->5->10 ( order in which balloons are shot)

Maximum score =100

**TC 3:**

N=7

Arr= 12 48 28 21 67 75 85

way to get maximum score = 21->28->75->67->48->12->85 ( order in which balloons are shot)

Maximum score =16057

**TC 4:**

N=8

Arr=245 108 162 400 274 358 366 166

way to get maximum score = 162->108->274->358->400->366->166->245 ( order in which balloons are shot)

Maximum score =561630