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

/* def: Postoji inverzija niza a[0..n) izmedju i i j ako i < j i a[i] > a[j].
 *
 * Zadatak: Odrediti broj inverzija niza a[0..).
 *
 *       i: 0  1  2  3  4  5  6  7  8  9
 *  vec[i]: 3  1  4  1  5  9  2  6
 * freq[i]: 0  1  0  1  1  0  0  0  0  0        (freq : SegmentTree)
 *   count: 0 +1 +0 +2 +0 +0 +4 +1 = 8
 *                   |-> Koliko ima većih od 1 pre 1?
 *                       Kako dobiti odgovor preko sume? freq->sum(2, 9)
 *                       Šta onda čuvati u segmentnom stablu? 
 *                          Frekvenciju elemenata do i-tog elementa
 */

class SegmentTree
{
public:
    SegmentTree(int n)
    {
        n = std::pow(2, std::ceil(std::log2(n)));
        m_tree.resize(2 * n);
        std::fill(m_tree.begin(), m_tree.end(), 0);
    }

    int sum(int a, int b) 
    {
        const int n = m_tree.size() / 2;

        int l = n + a, r = n + b;
        int sum = 0;

        while (l <= r) {
            if (l % 2 != 0) sum += m_tree[l++];
            if (r % 2 == 0) sum += m_tree[r--];
            l /= 2; r /= 2;
        }

        return sum;
    }

    void update(int i)
    {
        const int n = m_tree.size() / 2;

        int k = n + i;
        m_tree[k]++;

        k /= 2;
        while (k > 0) {
            m_tree[k] = m_tree[2 * k] + m_tree[2 * k + 1];
            k /= 2;
        }
    }

    ~SegmentTree() {}

protected:
    std::vector<int> m_tree;
};

int main(void)
{
    std::vector<int> vec = { 3, 1, 4, 1, 5, 9, 2, 6 };

    int max = *std::max_element(vec.begin(), vec.end());

    auto tree = new SegmentTree(max);

    int count = 0;
    for (int i = 0; i < vec.size(); i++) {
        count += tree->sum(vec[i] + 1, max);
        tree->update(vec[i]);
    }

    std::cout << count << std::endl;

    return 0;
}