Minh là một học sinh rất yêu thích lập trình, em đã tạo ra một Game X nhằm giúp người chơi phát triển tư duy toán học.

Game được mô tả như sau: Cho trước \(n\) tấm thẻ hình chữ nhật được đánh số thứ tự từ \(1\) đến \(n\), tấm thẻ thứ \(i\) ghi một số nguyên dương \(a_{i}\). Mỗi lượt chơi, người chơi cần chọn số lượng tấm thẻ nhiều nhất có thể và tuân thủ tất cả các quy tắc của trò chơi như sau:

• Chọn ra một số tấm thẻ xếp thành một hàng ngang, sao cho thứ tự các tấm thẻ tăng dần từ trái qua phải;

• Tấm thẻ \(i,\ j\ (1 \leq i,j \leq n)\) xếp cạnh nhau cần thỏa các điều kiện:

  • \(0 < |j - i| \leq 10\);

  • \(\left| a_{j} - a_{i} \right| > 0\);

  • \(\left| a_{j} - a_{i} \right|\) là bình phương của một số tự nhiên.

Yêu cầu: Cho biết số lượng tấm thẻ nhiều nhất mà người chơi có thể chọn được trong mỗi lượt chơi.

Dữ liệu vào:

+ Dòng thứ nhất chứa duy nhất số nguyên dương \(n\ \left( 1 < n \leq 10^{5} \right)\);

+ Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa số nguyên dương \(a_{i}\ (1 \leq a_{i} \leq 10^{9})\).

Kết quả ra:

+ Ghi một số nguyên dương duy nhất thỏa mãn yêu cầu bài toán.

Ví dụ:

Ràng buộc dữ liệu:

• \(25.0\%\) tests ứng với: \(1 < n \leq 20,\ 0 < a_{i} \leq 10^{9}\);

• 37.5% tests ứng với: \(1 < n \leq 10^{3},\ 0 < a_{i} \leq 10^{9}\);

• 37.5% tests ứng với: \(1 < n \leq 10^{5},\ 0 < a_{i} \leq 10^{9}\).