Trò chơi xếp thẻ

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

Trò chơi đượ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 số thứ tự của các tấm thẻ tăng dần từ trái qua phải (giá trị $a_i$ ghi trên thẻ không cần tăng dần).
• Hai tấm thẻ $i,j$ ($1\le i,j\le n$) xếp cạnh nhau trong hàng cần thỏa mãn các điều kiện:
  • $0<|j-i|\le 10$;
  • $|a_j-a_i|>0$;
  • $|a_j-a_i|$ là bình phương của một số tự nhiên.

Hàng chỉ gồm một tấm thẻ luôn hợp lệ.

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$ ($1<n\le {10}^5$).
• Dòng thứ $i$ trong $n$ dòng tiếp theo chứa số nguyên dương $a_i$ ($1\le a_i\le {10}^9$).

Dữ liệu ra

Ghi ra một số nguyên dương duy nhất là số lượng tấm thẻ nhiều nhất có thể chọn.

Ràng buộc

• $1<n\le {10}^5$.
• $1\le a_i\le {10}^9$.

Subtasks

• Subtask 1 ($25\%$ số điểm): $1<n\le 20$.
• Subtask 2 ($37.5\%$ số điểm): $1<n\le {10}^3$.
• Subtask 3 ($37.5\%$ số điểm): $1<n\le {10}^5$.

Ví dụ