#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
#include <algorithm>
#include <map>

#include "dzialka.h"
#include "message.h"


using std::vector;

//http://www.deltami.edu.pl/temat/informatyka/algorytmy/2015/10/27/Zliczamy_puste_prostokaty/

//int GetFieldHeight() {return 50000;}
//int GetFieldWidth() {return 50000;}
//int IsUsableCell(int r, int c) {return (r == c) ? 0 : 1;}

struct Rect {
    int w, h;
};

struct Stripe {
    int64_t total;
    vector<int> di;
    vector<int> Di;
    int height;
};

int64_t process(const vector<int>& di) {
    int64_t total = 0;
    std::stack< Rect, vector<Rect> > s;
    for (auto const &dij : di) {
        int w = 0;
        while (!s.empty() && s.top().h >= dij) {
            Rect sm = s.top();
            s.pop();
            int h = dij;
            if (!s.empty()) {
                if (h < s.top().h)
                    h = s.top().h;
            }
            w += sm.w;
            int64_t part = w * int64_t(w + 1) / 2 * (sm.h - h);
            total += part;
        }
        if (dij > 0) {
            if (s.empty() || s.top().h < dij) {
                s.push({w + 1, dij});
            }
        }
    }
    return total;
}

Stripe delta(int iBegin, int iEnd) {
    const int width = GetFieldWidth();
    Stripe result;

    result.total = 0;
    result.di.resize(width + 2);
    result.Di.resize(width + 2);
    result.height = iEnd - iBegin;

    for (int i = iBegin; i < iEnd; i++) {
        for (int j = 0; j < width; j++) {
            bool usable = IsUsableCell(i, j) == 1;
            if (usable) {
                result.di[j + 1]++;
            } else {
                result.di[j + 1] = 0;
            }

            if (result.Di[j + 1] == (i - iBegin) && usable) {
                result.Di[j + 1]++;
            }
        }

        result.total += process(result.di);
    }

    return result;
}

int64_t process2(const std::map<int,int>& diComp) {
    int64_t total = 0;

    std::stack< Rect, vector<Rect> > s;

    auto i1 = diComp.begin();
    auto i2 = diComp.begin();
    int dij = 0;
    for (i2++; i1 != diComp.end(); ++i1, ++i2) {
        dij += i1->second;
        int cnt = 1;
        if (i2 != diComp.end())
            cnt = i2->first - i1->first;
        //std::cout << "C: "<< val << " " << cnt << std::endl;

        int w = 0;
        while (!s.empty() && s.top().h >= dij) {
            Rect sm = s.top();
            s.pop();
            int h = dij;
            if (!s.empty()) {
                if (h < s.top().h)
                    h = s.top().h;
            }
            w += sm.w;
            int64_t part = w * int64_t(w + 1) / 2 * (sm.h - h);
            total += part;
        }
        if (dij > 0) {
            //if (s.empty() || s.top().h < dij) {
                s.push({w + cnt, dij});
            //}
        }
    }
    return total;
}

int64_t merge_util(const vector<int>& ups, const vector<int>& dns) {

    int64_t total = 0;

    std::map<int,int> diComp0;
    for (int i=0; i < ups.size(); i++) {
        int zerosEnd = -ups[i];
        int incEnd = +dns[i];

        int sumBeg = 0;
        auto it = diComp0.begin();
        for (; it != diComp0.end() && it->first <= zerosEnd; ++it) {
            sumBeg += it->second;
        }
        diComp0.erase(diComp0.begin(), it);
        if (sumBeg + 1 != 0)
            diComp0[zerosEnd] = sumBeg + 1;

        auto newEnd = diComp0.lower_bound(incEnd);
        int sumEnd = 0;
        for (auto it = newEnd; it != diComp0.end(); ++it) {
            sumEnd += it->second;
        }
        diComp0.erase(newEnd, diComp0.end());
        if (sumEnd - 1 != 0)
            diComp0[incEnd] = sumEnd - 1;

        if (!diComp0.empty()) {
            total += process2(diComp0);
        }
    }
    return total;
}

int64_t mergeCnt(const vector<int>& a, const vector<int>& b) {
    // shit... I'm too old & stupid to implement it correctly in O(n) - let's go bruteforce
    int64_t AB = merge_util(a, b);
    int s = a.size();
    int64_t A = merge_util(a, vector<int>(s));
    int64_t B = merge_util(b, vector<int>(s));
    return AB - A - B;
}

const int every_n = 2000;
void sendStripes(int node, const vector<int>& a) {
    for (int i = 0; i < a.size(); i++) {
        PutInt(node, a[i]);
        if (!((i + 1) % every_n) && i || i == a.size() - 1) {
            Send(node);
        }
    }
}

vector<int> getStripes(int node, int size) {
    vector<int> a(size);
    for (int i = 0; i < size; i++) {
        if (i % every_n == 0) {
            Receive(node);
        }
        a[i] = GetInt(node);
    }
    return a;
}

void merge(vector<Stripe>& stripes) {

    int64_t total = 0;

//#define LOCAL

    //propagate closings
#ifdef LOCAL
    for (int i = stripes.size() - 2; i >= 0; i--) {
#else
    const int node = MyNodeId();
    const int nodes = NumberOfNodes();
    int i = node;

    if (node < nodes - 1) {
        stripes[i+1].Di = getStripes(node + 1, stripes[i].Di.size());
#endif
        for (int j = 0; j < stripes[i].Di.size(); j++) {
            if (stripes[i].Di[j] == stripes[i].height) {
                stripes[i].Di[j] += stripes[i+1].Di[j];
            }
        }
    }
#ifndef LOCAL
    if (node > 0) {
        sendStripes(node - 1, stripes[i].Di);
    }
#endif


#ifdef LOCAL
    for (int i=0; i<stripes.size()-1; i++) {
#else
    if (node < nodes - 1) {
#endif // LOCAL
        vector<int> opening = stripes[i].di;
        vector<int> closing = stripes[i+1].Di;

        for (int j=0; j<opening.size(); j++) {
            if (opening[j] == 0 || closing[j] == 0) {
                opening[j] = 0;
                closing[j] = 0;
            }
        }
        int64_t merged = mergeCnt(opening, closing);
        total += merged;
    }



#ifdef LOCAL
    for (int i=0; i < stripes.size(); i++) {
#endif // LOCAL
        total += stripes[i].total;
#ifdef LOCAL
    }
#endif // LOCAL

    if (node < nodes - 1) {
        PutLL(nodes - 1, total);
        Send(nodes - 1);
    } else {
        for (int i = 1; i < NumberOfNodes(); ++i) {
            int instancja = Receive(-1);
            int64_t subTotal = GetLL(instancja);
            total += subTotal;
        }
        std::cout << total << std::endl;
    }
}

int main() {
    //freopen("in/6.in", "r", stdin);

    const int height = GetFieldHeight();

    if (height < 5000) { //single instance should handle 5k, need to check correctness
        if (MyNodeId() == 0) {
            Stripe full = delta(0, height);
            std::cout << full.total << std::endl;
        }
        return 0;
    }

    int nodes = NumberOfNodes();

    vector<Stripe> stripes(nodes);
    //for (int node=0; node < nodes; node++)
    { //MyNodeId()
        const int node = MyNodeId();
        int poczatek = (node * height) / nodes;
        int koniec = ((node + 1) * height) / nodes;

        stripes[node] = delta(poczatek, koniec);
    }

    merge(stripes);
}