Cesenatico là một thành phố cảng của Ý bên bờ biển Adriatic, nổi tiếng với con kênh có nhiều thuyền neo đậu. Xét mô hình đơn giản sau: con kênh thẳng và chỉ một đầu thông ra biển. Trên kênh có \(N\) thuyền được đánh số từ \(1\) đến \(N\), ở các khoảng cách tăng dần \(A_1<A_2<\cdots<A_N\) tính từ biển. Để chuẩn bị cho lễ hội của thị trấn, bạn sơn mỗi thuyền bằng một trong \(N\) màu được đánh số từ \(1\) đến \(N\) sao cho không màu nào xuất hiện đúng một lần; một màu có thể không được dùng. Với mỗi màu xuất hiện ít nhất hai lần, dãy khoảng cách từ biển đến các thuyền mang màu đó, sau khi sắp xếp tăng dần, phải là một cấp số cộng.

Khoảng cách giữa hai thuyền phân biệt \(i,j\) là \(|A_i-A_j|\). Độ đẹp là khoảng cách nhỏ nhất giữa hai thuyền phân biệt cùng màu. Hãy tìm độ đẹp lớn nhất có thể, hoặc xác định không có cách tô hợp lệ.

Dữ liệu vào

Dòng đầu chứa \(N\). Dòng thứ hai chứa \(A_1,A_2,\ldots,A_N\).

Dữ liệu ra

In -1 nếu không có cách tô hợp lệ; ngược lại in độ đẹp lớn nhất.

Ràng buộc

• \(2 \le N \le 3500\).
• \(1 \le A_i\le10^9\).
• \(A_i<A_{i+1}\).
• Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(8\) điểm: \(A_i=i\).
2. \(11\) điểm: \(N\le7\).
3. \(12\) điểm: \(N\le100\).
4. \(39\) điểm: \(N\le700\).
5. \(30\) điểm: không có ràng buộc thêm.

Ví dụ

2
1 2

1

3
1 10 100

-1

5
5 6 8 9 11

3

Nguồn

JOI 2025/2026 - Vòng loại 2, bài Ship.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.