SHELF (Segment Tree - Sum)

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5 + 5;

int n, m;
ll a[N];
ll t[4 * N];

void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    }
    else {
        int tm = (tl + tr) / 2;
        build(v*2, tl, tm);
        build(v*2+1, tm+1, tr);
        t[v] = t[v*2] + t[v*2+1];
    }
}

ll sum(int v, int tl, int tr, int l, int r) {
    if (r < tl || tr < l) return 0;
    if (l <= tl && tr <= r) return t[v];

    int tm = (tl + tr) / 2;
    return sum(v*2, tl, tm, l, r) + sum(v*2+1, tm+1, tr, l, r);
}

void update(int v, int tl, int tr, int pos) {
    if (tl == tr) {
        ++t[v];
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos);
        else
            update(v*2+1, tm+1, tr, pos);
        t[v] = t[v*2] + t[v*2+1];
    }
}

int main()
{
    //freopen("in.txt", "r", stdin);
    freopen("SHELF.inp", "r", stdin);
    freopen("SHELF.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];

    build(1, 1, n);

    cin >> m;
    for(int i = 1; i <= m; ++i) {
        int x; cin >> x;

        ll ans = min(sum(1, 1, n, 1, x - 1), sum(1, 1, n, x + 1, n));
        cout << ans << ' ';
        update(1, 1, n, x);
    }

    return 0;
}