// Dmitry _kun_ Sayutin (2020)

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;
using std::queue;

using std::pair;
using std::make_pair;

using std::tuple;
using std::make_tuple;
using std::get;

using std::min;
using std::abs;
using std::max;
using std::swap;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}

#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

const int LOG = 20;
const int N = (1 << LOG);

typedef std::complex<double> cd;

int rev[N];
cd W[N];

void precalc() {
    const double pi = std::acos(-1);
    for (int i = 0; i != N; ++i)
        W[i] = cd(std::cos(2 * pi * i / N), std::sin(2 * pi * i / N));

    int last = 0;
    for (int i = 1; i != N; ++i) {
        if (i == (2 << last))
            ++last;

        rev[i] = rev[i ^ (1 << last)] | (1 << (LOG - 1 - last));
    }
}

void fft(vector<cd>& a) {
    for (int i = 0; i != N; ++i)
        if (i < rev[i])
            std::swap(a[i], a[rev[i]]);

    for (int lvl = 0; lvl != LOG; ++lvl)
        for (int start = 0; start != N; start += (2 << lvl))
            for (int pos = 0; pos != (1 << lvl); ++pos) {
                cd x = a[start + pos];
                cd y = a[start + pos + (1 << lvl)];

                y *= W[pos << (LOG - 1 - lvl)];
                
                a[start + pos] = x + y;
                a[start + pos + (1 << lvl)] = x - y;
            }
}

void inv_fft(vector<cd>& a) {
    fft(a);
    std::reverse(a.begin() + 1, a.end());
    
    for (cd& elem: a)
        elem /= N;
}

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // code here
    int root = 2;
    int mod = 200 * 1000 + 3;

    vector<int> logg(mod, -100);
    vector<int> poww(mod, -100);

    int64_t sum = 0;
    
    if (1) {
        int pw = 1;

        for (int i = 0; i <= mod - 2; ++i) {
            logg[pw] = i;
            poww[i] = pw;
            
            pw = (pw * 1ll * root) % mod;
        }
    }
    
    int n = input<int>();

    vector<cd> arr(1 << LOG);

    vector<int> in(n);
    for (int i = 0; i < n; ++i) {
        int val = input<int>();
        in[i] = val;
        
        if (val)
            arr[logg[val]] += 1;
    }

    precalc();
    fft(arr);
    for (int i = 0; i < SZ(arr); ++i)
        arr[i] *= arr[i];

    inv_fft(arr);

    for (int i = 0; i < SZ(arr); ++i) {
        sum += poww[i % (mod - 1)] * int64_t(round(arr[i].real()));
    }

    for (int i = 0; i < n; ++i)
        sum -= (in[i] * 1ll * in[i]) % mod;

    sum /= 2;

    // int64_t naive = 0;
    // for (int i = 0; i < n; ++i)
    //     for (int j = 0; j < i; ++j)
    //         naive += (in[i] * 1ll * in[j]) % mod;
    
    cout << (long long)sum << "\n";
    //cerr << (long long)naive << "\n";
    
    return 0;
}


Measured memory_bytes: 42808