Khi học về phép nội suy đa thức bằng đa thức nội suy Newton trên lưới đều. Toto rất thú vị áp dụng nó cho việc tìm số tiếp theo của dãy số như sau:

Cho một dãy \(n\) phần tử từ phần tử thứ \(0\) đến phần tử thứ \(n-1\) cần tìm phần tử thứ \(n\) biết rằng các phần tử theo quy luật của một đa thức bậc \(n-1\)

Ví dụ cho dãy số gồm 6 sau số đánh số từ 0 đến 5, cần tìm số thứ 6

\[ \begin{matrix} 4 & 10 & 26 & 58 & 112 & 194 & ? \\ \end{matrix} \]

Bước 1 Chúng ta lập bảng sai phân các cấp, cấp sau được tính dựa theo cấp trước bằng cách lấy giá trị sau trừ đi giá trị trước như minh họa dưới đây

Bước 2 Chúng ta tính cho cột cuối cùng bằng cách tính ngược lại từ dưới lên ban đầu sao chép giá trị cuối cột \(n-1\) sang cột n, sau đó làm quy trình cộng như minh họa

Bước 3 lấy kết quả ở cuối ta được giá trị tiếp theo phần tử thứ 6 là 310

Giải thích : Thực ra trong ví dụ này Toto đã có một đa thức bậc 3 \(P(x) = x^3+2x^2+3x+4\) nên \(P(6)= 310\)

Input

Dòng dầu chứa số nguyên dương \(n\) là số phần tử đầu của dãy \((3 \le n \le 12)\)

Dòng tiếp theo gồm n phần tử từ thứ \(0\) đến thứ \(n-1\) là các số nguyên có giá trị tuyệt đối không vượt quá \(100\)

Output

Một số nguyên là giá trị tiếp theo của dãy số biết rằng nó có giá trị tuyệt đối không vượt quá \(10^9\)

Ví dụ

Input

6
4   10  26  58  112 194

Output

310