THỰC HÀNH

Sau một thời gian sống với cuội ở gốc đa trên cung trăng, chị Hằng Nga thấy buồn chán và muốn mở cửa hàng buôn dưa lê. Chị Hằng Nga bắt Cuội làm cho một cái biển quảng cáo cho của hàng của mình. Cuội chỉ kiếm được mảnh gỗ trước đây là hàng rào vây gốc đa. Mảnh gỗ gồm n thanh gỗ ghép lại, mỗi thanh có chiều ngang là 1 đơn vị và chiều dài là h_i đơn vị, các thanh được ghép song song sát nhau và bằng nhau ở một đầu (như hình sau)

Trên cung trăng không có thước đo các loại nên Cuội chỉ có thể cưa tấm gỗ theo các đường ghép dọc là cạnh của các tấm gỗ (đường ngang phải có ít nhất một cạnh của tấm gỗ làm cữ). Hằng Nga lại yêu cầu bờm làm cho mình cái biển hình vuông có diện tích càng lớn càng tốt. Em hãy giúp Cuội tính diện tích tối đa của cái biến có thể làm được từ miếng gỗ trên nhé.

 Dữ liệu vào:

• Dòng đầu chứa số nguyên dương n (là số thanh gỗ của mảnh gỗ).
• Dòng 2 chứa n số nguyên dương h₁, h₂, …, h_n. Hai số liên tiếp cách nhau một dấu cách.

Dữ liệu ra:

Một số nguyên dương duy nhất là diện tích của tấm biển lớn nhất có thể.

Ví dụ:

Dữ liệu vào:
7
5 2 4 3 3 1 4
Dữ liệu ra:
9

Giải thích: Phương án tối ưu được mô tả trong hình sau (ô màu xanh là biển làm được):

Giới hạn: 1 ≤ n ≤ 10⁶; 1 ≤ h_i ≤ 10⁹.