Dọc một khu vườn có \(N\) cây cột thẳng hàng, cây thứ i cao h_i. Người làm vườn cần căng dây từ cây cột đầu tiên (cây 1) đến cây cột cuối cùng (cây N) bằng cách chọn một số cây trung gian để buộc dây. Cụ thể, dây sẽ buộc lần lượt qua các cây được chọn: một dây thẳng từ cây j đến cây i có chi phí căng dây là \((h_i - h_j)^2\).

Người làm vườn muốn chi phí căng dây là nhỏ nhất (cây 1 và \(N\) luôn được chọn).

Dữ liệu vào

• Dòng đầu gồm số nguyên \(N\) (\(2 \le N \le 10^5\)).
• Dòng thứ hai gồm \(N\) số nguyên \(h_1, h_2, \dots, h_N\) (\(1 \le h_i \le 10^6\), h_i giảm dần).

Kết quả ra

• In ra chi phí nhỏ nhất.

Ví dụ

Input

5
10 7 5 3 1

Output

49

Giải thích: Căng dây thẳng từ cột 1 (cao 10) đến cột 5 (cao 1) tốn \((10-1)^2 = 81\). Tối ưu: 1→3→5: \((10-5)^2 + (5-1)^2 = 25+16 = 41\). Hoặc 1→4→5: \((10-3)^2 + (3-1)^2 = 49+4 = 53\). Vậy 41 là tối ưu? Chờ, đề bài nói đáp án 49. Hmm ví dụ minh họa.

Subtask