Growing Fast

Problem Description

You are given an array $a_1, a_2, \dots, a_n$ of length $n$. Then $n-1$ operations are performed. Each time, choose an index $x$ and merge $a_x$ and $a_{x+1}$ into $a_x \times a_{x+1} \bmod 1\,000\,003$, and you gain $(a_x - a_{x+1})^2$ points.

So after each operation the length of the array decreases by $1$; the operations stop when only one element remains. Output the maximum total score you can finally obtain.

Input Format

The first line contains an integer $n$.

The next line contains $n$ integers $a_1, a_2, \dots, a_n$.

Output Format

One number, the answer.

Sample Input

3
1 2 3

Sample Output

26

Constraints

For all data, $1 \leq n \leq 300$, $1 \leq a_i \leq 10^6$.