Quảng Nam là mảnh đất hiếu học. Trường THCS Nguyễn Du là nơi nuôi dưỡng ước mơ của cậu bé An. Em là người đam mê Tin học và rất giỏi lập trình nên các bạn thường gọi em là “siêu nhân Tin”. Được nghe danh tiếng của An, các anh chị khóa trước tìm đến và nhờ em giải giúp bài toán về chuyên đề “dãy số”. Nội dung cụ thể bài toán như sau:

“Cho một dãy gồm \(n\) số tự nhiên \(a_{i}\ (i\ = 1,\ 2,\ \ldots,\ n)\). Hãy lập trình tính tổng các số chính phương không xuất hiện trong dãy sao cho các số này không vượt quá giá trị lớn nhất có mặt trong dãy đó”. (Số chính phương là số tự nhiên có căn bậc hai là một số tự nhiên, hay nói cách khác, số chính phương bằng bình phương của một số nguyên).

Yêu cầu: Bạn nghĩ xem, An sẽ làm cách nào để giúp anh chị khóa trước tìm ra kết quả của bài toán?

Dữ liệu vào:

+ Dòng thứ nhất ghi giá trị của \(n\ (0\ < \ n\ \leq \ 10^{6})\);

+ Dòng thứ hai, ghi \(n\) số tự nhiên \(a_{i}\) của dãy \((0\ \leq \ a_{i}\ \leq \ 10^{9})\) các số cách nhau một khoảng trắng.

Kết quả:

+ Ghi một dòng là đáp án cần tìm.

Ví dụ:

Ràng buộc:

• Có 40% test tương ứng 40% số điểm của bài với \(n\ \leq \ 10^{3},0\ \leq \ a_{i}\ \leq \ 10^{4}\);

• Có 30% test tương ứng 30% số điểm của bài với \(n\ \leq \ 10^{4},\ 0\ \leq \ a_{i}\ \leq \ 10^{6}\);

• Có 30% test tương ứng 30% số điểm của bài với \(n\ \leq \ 10^{6},\ 0\ \leq \ a_{i}\ \leq \ 10^{9}\).