CF1879D

// Problem: D. Sum of XOR Functions
// Contest: Codeforces - Educational Codeforces Round 155 (Rated for Div. 2)
// URL: https://codeforces.com/problemset/problem/1879/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using a2l = array<ll, 2>;
using pll = pair<ll, ll>;
using vl = vector<ll>;

constexpr ll mod = 998244353;

void solve_edt()
{
    ll n, ans = 0;
    cin >> n;
    vl a(n);
    for (auto &x : a)
        cin >> x;

    /*
    for (ll i = 1; i < n; ++i)
        a[i] ^= a[i - 1];
    */

    auto count_bit = [&](ll b) {
        ll ret = 0;
        ll sum[2] = {0, 0}, cnt[2] = {1, 0};
        for (ll i = 0, acc = 0; i < n; ++i) {
            ll v = a[i] >> b & 1;
            // ll flag = acc % 2;
            ll pf = acc % 2;
            acc = acc + v;
            ll flag = acc % 2;
            // ll d = (i + 1) * (cnt[1 - flag] + v) - sum[1 - flag];
            ll d = (i + 1) * cnt[1 - flag] - sum[1 - flag];
            dbg(flag, v, d);
            dbg(i + 1, cnt[1 - flag], sum[1 - flag]);
            // sum[flag] += i + 1, cnt[flag] += 1;
            sum[flag] += i + 1, cnt[flag] += 1;
            // sum[pf] += i, cnt[pf] += 1;
            dbg(d);
            ret = (ret + d) % mod;
        }
        return (ret << b) % mod;
    };

    for (ll i = 0; i < 31; ++i)
        ans = (ans + count_bit(i)) % mod;
    cout << ans << '\n';
}

void solve()
{
    ll n, ans = 0;
    cin >> n;
    vl a(n);
    for (auto &x : a)
        cin >> x;

    auto count_bit = [&](ll b) {
        ll ret = 0;
        vl acc(n), oc(n), ec(n), os(n), es(n);
        for (ll i = 0; i < n; ++i) {
            ll c = (a[i] >> b) & 1;
            acc[i] = c + (i > 0 ? acc[i - 1] : 0);
        }
        for (ll i = n - 1; i >= 0; --i) {
            ll v = acc[i] % 2;
            oc[i] = (i < n - 1 ? oc[i + 1] : 0) + v;
            ec[i] = (i < n - 1 ? ec[i + 1] : 0) + 1 - v;
            os[i] = (i < n - 1 ? os[i + 1] : 0) + (v ? i : 0);
            es[i] = (i < n - 1 ? es[i + 1] : 0) + (1 - v ? i : 0);
        }
        for (ll i = 0, zc = 0; i < n; ++i) {
            ll flag = (a[i] >> b) & 1;
            zc += 1;
            if (flag) {
                const auto &vs = acc[i] % 2 ? os : es;
                const auto &cs = acc[i] % 2 ? oc : ec;
                auto v = vs[i] + cs[i];
                auto d = (v * zc - cs[i] * zc * (i + i - zc + 1) / 2) % mod;
                dbg(d, v, zc);
                ret = (ret + d) % mod;
                zc = 0;
            }
        }
        return (ret << b) % mod;
    };
    for (ll i = 0; i < 31; ++i)
        ans = (ans + count_bit(i)) % mod;
    cout << ans << '\n';
}

void solve_wa()
{
    ll n, ans = 0;
    cin >> n;
    vl a(n);
    for (auto &x : a)
        cin >> x;

    auto count_bit = [&](ll b) {
        ll ret = 0;
        vl acc(n), oc(n), ec(n);
        for (ll i = 0; i < n; ++i) {
            ll c = (a[i] >> b) & 1;
            acc[i] = c + (i > 0 ? acc[i - 1] : 0);
        }
        for (ll i = n - 1; i >= 0; --i) {
            ll v = acc[i] % 2;
            oc[i] = (i < n - 1 ? oc[i + 1] : 0) + v;
            ec[i] = (i < n - 1 ? ec[i + 1] : 0) + 1 - v;
        }
        for (ll i = 0, zc = 0; i < n; ++i) {
            ll flag = (a[i] >> b) & 1;
            zc += 1;
            if (flag) {
                const auto &vs = acc[i] % 2 ? oc : ec;
                auto v = vs[i];
                auto gain = v * (v + 1) / 2;
                auto gain2 = (gain + gain + v * (zc - 1)) * zc / 2;
                if (b == 1)
                    dbg(gain2);
                ret = (ret + gain2) % mod;
                zc = 0;
            }
        }
        if (b == 1) {
            dbg(acc);
            dbg(ec);
            dbg(oc);
        }
        return (ret << b) % mod;
    };
    for (ll i = 0; i < 31; ++i)
        ans = (ans + count_bit(i)) % mod;
    cout << ans << '\n';
}

int main(int argc, char **argv)
{
    solve_edt();
    return 0;
};