// C++ Program of the above approach
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

// Defining Policy Based Data Structure
typedef tree<int, null_type,
             less_equal<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;

// Function to count points
// of intersection of pairs
// (a, b) and (c, d)
// such that a > c and b < d
int cntIntersections(
    vector<pair<int, int> > lines,
    int N)
{
    // Stores the count
    // of intersection points
    int cnt = 0;

    // Initializing Ordered Multiset
    ordered_multiset s;

    // Loop to iterate the array
    for (int i = 0; i < N; i++) {

        // Add the count of integers
        // smaller than lines[i].second
        // in the total count
        cnt += s.order_of_key(lines[i].second);

        // Insert lines[i].second into s
        s.insert(lines[i].second);
    }

    // Return Count
    return cnt;
}

// Function to find the
// total count of points of
// intersections of all the given lines
int cntAllIntersections(
    vector<pair<int, int> > lines,
    int N)
{
    // Sort the array in decreasing
    // order of 1st element
    sort(lines.begin(), lines.end(),
         greater<pair<int, int> >());

    // Stores the total count
    int totalCnt = 0;

    // Function call for cases
    // with a > c and b < d
    totalCnt += cntIntersections(lines, N);

    // Swap all the pairs of the array in order
    // to calculate cases with a < c and b > d
    for (int i = 0; i < N; i++) {
        swap(lines[i].first, lines[i].second);
    }

    // Function call for cases
    // with a < c and b > d
    totalCnt += cntIntersections(lines, N);

    // Return Answer
    return totalCnt;
}

// Driver Code
int main()
{
    vector<pair<int, int> > lines{
        {1, 5}, {2, 1}, {3, 7}, {4, 1}, {8, 2}
    };

    cout << cntAllIntersections(lines,
                                lines.size());

    return 0;
}

5