Thành phố H có ~n~ khu vực được xếp trên một đường thẳng. Đối chiếu hệ trục tọa độ ~Ox~ trên bản thiết kế, ta có khu vực thứ ~i~ sẽ ở vị trí ~x_i~. Hiện tại, khu vực 1 và khu vực ~n~ đang có trạm biến áp (TBA) đặt tại hai nơi này. Kế hoạch nâng cấp hệ thống lưới điện sẽ được tiến hành như sau:

• Sau khi hoàn thành nâng cấp, mỗi khu vực phải có TBA đặt ở tại nơi đó.
• Trong quá trình nâng cấp, nhân viên điện lực sẽ chọn một khu vực ~j~ bất kỳ chưa có TBA và tiến hành lắp đặt tại đó. Khi lắp xong TBA, nhân viên phải nối dây tới hai TBA gần nhất ở hai phía bên trái và bên phải. Lúc này, chi phí dùng để nối điện là một số đúng bằng bình phương khoảng cách của hai TBA gần nhất ở hai phía bên trái và bên phải. Nghĩa là, nếu lắp TBA ở ~x_i~ thì chi phí là ~|x_r - x_l|^2~, với ~x_l, x_r~ lần lượt là vị trí của hai TBA gần nhất ở phía bên trái và bên phải so với ~x_i~.

Yêu cầu: Bạn hãy tính chi phí tối thiểu để nâng cấp hệ thống lưới điện của công ty.

Dữ liệu

• Dòng thứ nhất chứa số nguyên dương ~n~ là số khu vực trong thành phố Hội An.
• Dòng thứ hai chứa ~n~ số nguyên dương ~1 \le x_1 < x_2 < \dots < x_n \le 10^6~ là vị trí của các khu vực trong thành phố Hội An.

Kết quả

Gồm dòng duy nhất chứa một số nguyên dương là chi phí tối thiểu để nâng cấp hệ thống lưới điện.

Ví dụ

TBA.INP

5
3 5 9 10 15

TBA.OUT

216

Giải thích: Trong ví dụ, có thể chọn khu vực theo thứ tự ~3 \to 2 \to 4~ sẽ cho ra chi phí nhỏ nhất là ~|15 - 3|^2 + |9 - 3|^2 + |15 - 9|^2 = 216~.

Giới hạn

• Có 40% số test tương ứng 40% số điểm của bài với ~1 \le n \le 15~;
• Có 40% số test tương ứng 40% số điểm của bài với ~1 \le n \le 500~;
• Có 20% số test tương ứng 20% số điểm của bài với ~1 \le n < 5000~.