#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <list>
using namespace std;

void izpisi(vector<int> v) {
    for (int x : v) cout << x << " ";
    cout << endl;
}

class RMQ {
private:
    int n;
    int INF=1000000000;
    vector<int> array;
    struct Node { int min, begin, end; };
    vector<Node> tree;

public:
    RMQ(vector<int> a) {
        n=pow(2,ceil(log2(a.size())));
        array = a;
        array.resize(n,INF);
        tree.resize(2*n);
        build();
    }

    void build(int id=1) {
        if (id>=n) {
            tree[id] = {array[id-n], id-n, id-n+1};
            return;
        }
        int left=id*2, right=id*2+1;
        build(left); build(right);
        tree[id] = {min(tree[left].min, tree[right].min),
                    tree[left].begin,
                    tree[right].end};
    }

    int query(int l, int r, int id=1) {
        if (l<=tree[id].begin && tree[id].end<=r) { // znotraj
            return tree[id].min;
        }
        if (r<=tree[id].begin || tree[id].end<=l) { // zunaj
            return INF;
        }
        return min(query(l,r,id*2), query(l,r,id*2+1));
    }

};

int main() {
    default_random_engine rnd(123);
    vector<int> v; //= {6,8,4,5,2,6,3,7,1,2,9,2,7,8,4,2};
    int n=1000000;
    for (int i=0;i<n;i++) v.push_back(rnd()%1000000000);
    RMQ rmq(v);
    int x=0;
    for (int it=0;it<1000000;it++) {
        int l=rnd()%n, r=rnd()%n;
        if (r<=l) continue;
        //int m = *min_element(v.begin()+l, v.begin()+r);
        //if (rmq.query(l,r) != m) cout << "UPS" << endl;
        x+=rmq.query(l,r);
    }
    cout << x << endl;
    return 0;
}