#include <iostream>
#include <stdio.h>
#include <stdint.h>
#include "message.h"
#include "teatr.h"

inline int max(int a, int b) 
{ 
    return (a > b) ? a : b; 
} 

struct Node
{
    int key{0};
    int height{1};
    int size{1};
    Node* left{nullptr};
    Node* right{nullptr};

    void update()
    {
        int lh = 0, ls = 0;
        int rh = 0, rs = 0;
        if (left != nullptr)
        {
            lh = left->height;
            ls = left->size;
        }
        if (right != nullptr)
        {
            rh = right->height;
            rs = right->size;
        }

        height = max(lh, rh) + 1;
        size = ls + rs + 1;
    }

    int getBalance()
    {
        int lh = 0, rh = 0;
        if (left != nullptr)
            lh = left->height;
        if (right != nullptr)
            rh = right->height;
        return lh - rh;
    }

};

struct AVL
{
    Node* nodes{nullptr};
    int count{0};

    void reserve(int n)
    {
        nodes = new Node[n];
    }

    void clean()
    {
        delete[] nodes;
    }

    Node* add(int key)
    {
        Node* node = &nodes[count++];
        node->key = key;
        return node;
    }

    Node* rotateRight(Node* node)
    {
        Node* rootLeft = node->left;
        Node* right = rootLeft->right;

        rootLeft->right = node;
        node->left = right;

        node->update();
        rootLeft->update();
        return rootLeft;
    }

    Node* rotateLeft(Node* node)
    {
        Node* rootRight = node->right;
        Node* left = rootRight->left;

        rootRight->left = node;
        node->right = left;

        node->update();
        rootRight->update();
        return rootRight;
    }

    uint64_t getFights(Node* root, int key) 
    { 
        uint64_t result = 0;

        while (root != NULL) 
        {
            if (key <= root->key) 
                root = root->left; 
            else
            {
                result += (root->left != nullptr ? root->left->size : 0) + 1;
                root = root->right;
                
            }
        } 
        return result; 
    } 

    Node* insert(Node* root, int key, uint64_t* counter)
    {
        if (root == nullptr)
            return add(key);
        
        if (key <= root->key)
        {
            //printf("L\n");
            root->left = insert(root->left, key, counter);
        }
        else
        {
            //printf("R\n");
            root->right = insert(root->right, key, counter);

            int ls = 0;
            if (root->left != nullptr)
                ls = root->left->size;
            *counter += ls + 1;
        }

        root->update();

        int balance = root->getBalance();

        // Left Left Case 
        if (balance > 1 && key <= root->left->key)
        {
            //printf("R 1\n");
            return rotateRight(root); 
        }

        // Right Right Case 
        if (balance < -1 && key > root->right->key)
        {
            //printf("R 2\n");
            return rotateLeft(root); 
        }

        // Left Right Case 
        if (balance > 1 && key > root->left->key) 
        { 
            //printf("R 3\n");
            root->left =  rotateLeft(root->left); 
            return rotateRight(root); 
        } 

        // Right Left Case 
        if (balance < -1 && key <= root->right->key) 
        { 
            //printf("R 4\n");
            root->right = rotateRight(root->right); 
            return rotateLeft(root); 
        } 

        //printf("-\n");

        return root; 
    }
};

int main()
{
    AVL tree;

    int n = GetN();
    int chunk = n / NumberOfNodes();
    int from = MyNodeId() * chunk;
    int to = from + chunk;
    if (MyNodeId() == NumberOfNodes() - 1)
        to = n;

    tree.reserve(to - from);
    Node* root = nullptr;
    uint64_t total = 0;
    for (int i = to - 1; i >= from; --i)
    {
        uint64_t count = 0;
        root = tree.insert(root, GetElement(i), &count);
        total += count;
        //if (i % 1000000 == 0)
        //printf("[%d] %d - count: %lu\n", i, GetElement(i), count);
    }

    for (int i = from - 1; i >= 0; --i)
    {
        total += tree.getFights(root, GetElement(i));
    }

    if (MyNodeId() != 0)
    {
        PutLL(0, total);
        Send(0);
    }
    else
    {
        int counter = NumberOfNodes() - 1;
        while (counter > 0)
        {
            int sender = Receive(-1);
            total += GetLL(sender);
            --counter;
        }
        std::cout << total << std::endl;
    }

    tree.clean();
    return 0;
}