408364: GYM103107 D Doin' Time

One day, Fop_zz is playing a boring game merge numbers though he is busy.

There is a sequence $$$\{a_i\}$$$ of length $$$N$$$ and he should play this game for $$$n-1$$$ turns. In one turn, he chooses an index $$$x$$$ and then he merges $$$a_x$$$ and $$$a_{x+1}$$$ to $$$a_x \times a_{x+1} \bmod 1\,000\,003$$$ and gets $$$(a_x-a_{x+1})^2$$$ scores.

So, after one turn, the length of sequence will decrease exactly one, and after the last turn there's only $$$1$$$ integer in the sequence and he stops.

Now he want to know the maximum total scores he can get. Can you help him?

The first line contains one integer $$$N ~ (1 \leq N \leq 300)$$$ denoting the length of sequence.

The second line contains $$$N$$$ integers $$$a_1, a_2, \cdots, a_n ~ (1 \leq a_i \leq 10^6)$$$.

Output one line with only one integer denoting the answer.

3
1 2 3

26