Đống kẹo chính phương

Cho $n$ đống kẹo (với $n$ chẵn). Đống thứ $i$ chứa $a_i$ viên kẹo.

Trong một bước, bạn được chọn một đống bất kỳ rồi thêm một viên kẹo mới vào đống đó, hoặc bớt đi một viên (chỉ khi đống đang có ít nhất một viên).

Hãy tìm số bước ít nhất để sau khi thực hiện, có đúng $n/2$ đống mà số kẹo trong đống là số chính phương, và đúng $n/2$ đống còn lại có số kẹo không phải số chính phương.

Lưu ý: Số $0$ là số chính phương (vì $0=0^2$).

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên chẵn $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số nguyên duy nhất — số bước ít nhất cần thực hiện. Nếu trạng thái ban đầu đã thỏa mãn yêu cầu, in ra $0$.

Ràng buộc

• $2\le n\le 2·{10}^5$ và $n$ chẵn.
• $0\le a_i\le {10}^9$.

Ví dụ