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
115
116
117
118
119
120
121
122
#include "message.h"
#include "teatr.h"
#include <vector>
#include <map>
#include <iostream>

using namespace std;
int _mergeSort(vector<int>& arr, vector<int>& temp, int left, int right);
int merge(vector<int>& arr, vector<int>& temp, int left, int mid, int right);

int mergeSort(vector<int> arr, int array_size)
{
    vector<int> temp(array_size, 0);
    return _mergeSort(arr, temp, 0, array_size - 1);
}

int _mergeSort(vector<int>& arr, vector<int>& temp, int left, int right)
{
    int mid, inv_count = 0;
    if (right > left) {
        mid = (right + left) / 2;
        inv_count = _mergeSort(arr, temp, left, mid);
        inv_count += _mergeSort(arr, temp, mid + 1, right);
        inv_count += merge(arr, temp, left, mid + 1, right);
    }
    return inv_count;
}

int merge(vector<int>& arr, vector<int>& temp, int left, int mid, int right)
{
    int i, j, k;
    int inv_count = 0;

    i = left;
    j = mid;
    k = left;
    while ((i <= mid - 1) && (j <= right)) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        }
        else {
            temp[k++] = arr[j++];
            inv_count = inv_count + (mid - i);
        }
    }

    while (i <= mid - 1)
        temp[k++] = arr[i++];

    while (j <= right)
        temp[k++] = arr[j++];

    for (i = left; i <= right; i++)
        arr[i] = temp[i];

    return inv_count;
}
using namespace std;

pair<int,int> getminmax(int n){
  int max = 10000 * (n + 1) + 1;
  int min = 10000 * n + 1;
  return {min, max};

}
int main() {
  map<int, long long> quicker;
  bool solved = true;
  long long n = GetN();
  auto limits = getminmax(MyNodeId());

  long long ret = 0;
  for(int i = 0; i < n; i ++){
    long long greater = 0;
    int tmp = GetElement(i);
    if(quicker.size() > 6){
      solved = false;
      break;
    } else {
      if(tmp > limits.second){
        greater ++;
      } else if (tmp >= limits.first){
        ret += greater;
        quicker[tmp] ++;
        for(const auto& a : quicker){
          if(a.first > tmp){
            ret += a.second;
          }
        }
      }

    }
  }
  if(!solved){
    vector<int> arr;
    ret = 0;
    long long greater = 0;
    for(long long i = 0; i < n; i ++){
      int tmp = GetElement(i);
      if(tmp > limits.second){
        greater ++;
      } else if (tmp >= limits.first){
        ret += greater;
        arr.push_back(tmp);
      }
    }
    ret += mergeSort(arr,  arr.size());
  }
  if(MyNodeId() == 0){
    for(long long k = 1; k < NumberOfNodes(); k ++){
      Receive(k);
      long long cur = GetLL(k);
      ret += cur;
    }
    cout << ret << endl;
  } else {

    PutLL(0, ret);
    Send(0);
  }

}