e.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

typedef int Int;

Int sqr(Int x) {
    return x * x;
}

Int low_sqr(Int x) {
    return sqr(Int(std::floor(std::sqrt(x))));
}

Int high_sqr(Int x) {
    return sqr(Int(std::ceil(std::sqrt(x))));
}

struct Pair {
    Int value, dist;

    Pair(Int v)
        : value(v)
        , dist(
            std::min(
                std::abs(v-high_sqr(v)),
                std::abs(v-low_sqr(v))
            )
        )
    { }

    Pair(Int v, Int dist)
        : value(v)
        , dist(dist)
    { }
};

int main() {
//  freopen("input.txt", "rt", stdin);

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);

    Int n;
    std::cin >> n;

    std::vector<Pair> a;
    a.reserve(n);

    for (Int i = 0; i < n; ++i) {
        Int v;
        std::cin >> v;
        a.push_back(Pair(v));
    }

    // Вначале лежат полные квадраты
    std::sort(a.begin(), a.end(), [](const Pair& a, const Pair& b) {
        return a.dist < b.dist || (a.dist == b.dist && a.value == 0);
    });

    auto it = a.begin();
    for (int i = 0; i < n / 2; ++i) {
        it++;
    }

    // Если после половины остались нули, убираем их в конец
    std::sort(it, a.end(), [](const Pair& a, const Pair& b) {
        return a.dist < b.dist || (a.dist == b.dist && b.value == 0);
    });

    // Из первой половины делаем полные квадраты
    Int answ = 0;
    for (Int i = 0; i < n / 2; ++i) {
        answ += a[i].dist;
    }

    // Вторые изменяем на неполные квадраты
    for (Int i = n / 2; i < n; ++i) {
        if (a[i].value == 0) {
            answ += 2;
        } else if (a[i].dist == 0) {
            answ++;
        }
    }
    std::cout << answ;

    return 0;
}