1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
#include "message.h"
#include "teatr.h"
using namespace std;

#define THRREP(msg) clog << "" << MyNodeId() << " " << msg << endl
#define THRPHS(phs) THRREP("Phase " phs " completed")

template <typename T> struct IndexRange {
    struct Iterator {
        T i;
        const T& operator*() const { return i; }
        Iterator& operator++() { ++i; return *this; }
        friend bool operator!=(const Iterator& a, const Iterator& b) { return a.i != b.i; }
    };
    T left, right;
    Iterator begin() const { return Iterator{left}; }
    Iterator end() const { return Iterator{right}; }
    bool empty() const { return left == right; }
};
template <typename T, typename U, typename V> IndexRange<T> workloadRange(T n) {
    return IndexRange<V>{(V)((U)MyNodeId()*n/NumberOfNodes()), (V)((U)(MyNodeId()+1)*n/NumberOfNodes())};
}

template <typename T> struct BinaryTreeReporter {
    BinaryTreeReporter(){}
    void send(T x) {
        r = move(x);
        auto v = MyNodeId()+1;
        if (2*v <= NumberOfNodes())
            r = T::merge(r, wrecv(2*v-1));
        if (2*v+1 <= NumberOfNodes())
            r = T::merge(r, wrecv(2*v+1-1));
        if (v != 1)
            wsend(v/2-1, r);
    }
    bool isRoot() {
        return MyNodeId() == 0;
    }
    const T& receive() {
        return r;
    }
private:
    T wrecv(int w) {
        Receive(w);
        return T::gcjGet(w);
    }
    void wsend(int w, const T& x) {
        x.gcjPut(w);
        Send(w);
    }
    T r;
};

struct I32SumSegtree {
    I32SumSegtree(int n):base(1){
        while (base < n) base *= 2;
        nodes.resize(base*2, 0);
    }
    void incLeaf(int i) {
        for (auto v=base+i; v>0; v>>=1)
            ++nodes[v];
    }
    int sumPrefix(int right) const {
        auto r = 0;
        for (auto vr=base+right; 1<vr; vr>>=1)
            if (vr & 1) r += nodes[--vr];
        return r;
    }
    int base;
    vector<int> nodes;
};

const int VALUE_MAX = 1000000;

vector<int> countOnRange(int left, int right) {
    auto cnt = vector<int>(VALUE_MAX+1, 0);
    for (auto i=left; i<right; ++i)
        ++cnt[GetElement(i)];
    return cnt;
}

template <typename T> vector<T> suffixSum(vector<T> xs) {
    for (auto i=(int)xs.size()-2; i>=0; --i)
        xs[i] += xs[i+1];
    return xs;
}

struct Report {
    long long result;
    static Report merge(const Report& a, const Report& b) { return Report{a.result + b.result}; }
    static Report gcjGet(int w) { return Report{GetLL(w)}; }
    void gcjPut(int w) const { PutLL(w, result); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    auto workload = workloadRange<int, long long, int>(GetN());
    auto counts = countOnRange(0, workload.left);
    auto farTall = suffixSum(move(counts));
    auto nearTall = I32SumSegtree(VALUE_MAX+2);
    auto result = 0ll;
    for (auto i : workload) {
        auto x = GetElement(i);
        if (x < VALUE_MAX)
            result += farTall[x+1] + nearTall.sumPrefix(VALUE_MAX-x);
        nearTall.incLeaf(VALUE_MAX-x);
    }
    auto reporter = BinaryTreeReporter<Report>();
    reporter.send(Report{result});
    if (reporter.isRoot())
        cout << reporter.receive().result << '\n';
}