Hotspot là một địa điểm vật lý nơi mọi người thường có thể sử dụng Wi-Fi để truy cập Internet thông qua mạng cục bộ không dây (WLAN) với bộ định tuyến kết nối với nhà cung cấp dịch vụ Internet. Hầu hết mọi người gọi những nơi này là "điểm phát Wi-Fi". Các hotspot công cộng thường được tạo ra từ các điểm truy cập không dây, gọi tắt là AP. Cụ thể, một hotspot là một vùng nằm trong khoảng cách $r$ tính từ vị trí lắp đặt AP. Nói cách khác, đó là một hình tròn có bán kính $r$ với tâm tại vị trí của AP.

Trong một thành phố, có một con đường thẳng dài. Các AP đã được lắp đặt dọc theo con đường này. Các quan chức thành phố cần thiết lập bán kính cho các hotspot. Khi đó, đối với bất kỳ hai AP khác nhau nào, các hotspot được tạo ra từ chúng không được chồng lấp lên nhau, nhưng chúng có thể tiếp xúc tại biên. Một trường hợp đặc biệt là nếu bán kính của một hotspot bằng 0, và một hotspot khác chứa nó bên trong, thì hai hotspot đó được coi là chồng lấp, và điều này không được phép xảy ra. Tuy nhiên, ngay cả khi bán kính của hotspot bằng 0, hotspot đó vẫn có thể chạm vào biên của một hotspot khác.

Các quan chức thành phố đang cố gắng thiết lập bán kính của các hotspot sao cho tổng diện tích bao phủ của chúng là lớn nhất có thể. Do đó, họ cần tối đa hóa tổng diện tích của các hotspot, đơn giản là tổng bình phương các bán kính của các hotspot. Để đạt được mục tiêu này, một số bán kính của các hotspot có thể được đặt bằng 0.

Con đường được coi là một đường thẳng trên mặt phẳng, và các vị trí của các AP được lắp đặt trên con đường là các điểm trên đường thẳng đó. Hãy viết một chương trình, với $n$ điểm cho trước trên đường thẳng, xác định bán kính của các hotspot không chồng lấp sao cho tổng bình phương các bán kính này là lớn nhất có thể.

Ví dụ, có ba AP nằm tại 0, 2 và 5 như trong hình trên. Một phương án là các hotspot màu xanh dương và màu đỏ. Bán kính của các hotspot màu xanh dương lần lượt là 1, 1 và 2 từ trái sang phải. Khi đó tổng bình phương các bán kính là 6. Nhưng đối với các hotspot màu đỏ, bán kính của chúng lần lượt là 2, 0 và 3 từ trái sang phải. Do đó, tổng bình phương các bán kính là 13, đây là giá trị lớn nhất.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $n$, số lượng AP ($2 \le n \le 3 \cdot 10^5$). Dòng thứ hai chứa $n$ số nguyên phân biệt cách nhau bởi dấu cách theo thứ tự tăng dần nghiêm ngặt, đại diện cho vị trí của các AP trên đường thẳng, trong đó các số nguyên nằm trong khoảng từ 0 đến $10^9$ bao gồm cả hai đầu.

Dữ liệu ra

In ra một số nguyên duy nhất: tổng bình phương lớn nhất có thể của các bán kính hotspot.

Ví dụ

Ví dụ 1

3
0 2 5

13

Ví dụ 2

4
0 1 3 6

10

Ví dụ 3

5
5 7 12 13 15

9