<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

512. Friendly Points
Time limit per test: 2.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Consider n distinct points on a plane.

Two points from that set are said to be friends, when there exists a rectangle with sides parallel to coordinate axes that contains those two points and doesn't contain any other point from the given set. A rectangle is said to contain a point if the point lies within the rectangle or on its border.

How many pairs of friends are there among the given points?

Input
The first line of the input file contains an integer n <= 100 000.

The next n lines contain two integers each, the coordinates of the given points. The coordinates don't exceed 10^9 by absolute value.

Output
Output one integer number — the sought number of pairs of friends.

Example(s)
sample input
sample output
5
0 0
0 2
2 0
2 2
1 1
8

<|response|>
1. Abridged problem statement
You have n distinct points on the plane. Call a pair of points (p, q) "friends" if you can draw an axis‐aligned rectangle that contains p and q (on its border or inside) and contains no other given point. Count the number of unordered friendly pairs.

2. Key observations
- The minimal axis‐aligned rectangle spanning p=(x₁,y₁) and q=(x₂,y₂) has corners (min x, min y) to (max x, max y). It will contain exactly p and q iff no other point lies in the x‐interval [min x, max x] with y between min y and max y.
- We can sort points by x, group by equal x, and do a divide‐and‐conquer on these x‐groups.
- In the recursive step, after counting pairs entirely in the left half and entirely in the right half, we need to count "cross‐pairs" with one point in the left half L and one in the right half R.
- For a candidate pair (ℓ∈L, r∈R), emptiness of the rectangle is equivalent to:
  • No other L‐point whose x≥ℓ.x has y between ℓ.y and r.y.
  • No other R‐point whose x≤r.x has y between ℓ.y and r.y.
- We can handle all cross‐pairs in O(|L|+|R|) per recursive level by two sweeps over R sorted by y: one for ℓ.y ≥ r.y and one for ℓ.y ≤ r.y, maintaining a "Pareto frontier" of L‐points (those not dominated in x‐coordinate) and a frontier of R‐points for exclusion of already‐counted intervals.

3. Full solution approach
A. Preprocessing
  1. Read n points, group them by x‐coordinate, and sort the distinct x‐values.
  2. Build a vector of groups, each group is all points with the same x, in increasing x‐order.

B. Divide‐and‐conquer function dc(groups):
  Base case: if there is only one x‐group G, then on this vertical line any two adjacent points in sorted‐by‐y order form a friendly pair and no other pairs do. So return |G| – 1.

  Otherwise:
  1. Split groups into left half L and right half R (by index).
  2. Recurse: ans = dc(L) + dc(R).
  3. Count cross‐pairs between L and R:
     a. Flatten L and R into lists Lpts and Rpts.
     b. SWEEP #1 for ℓ.y ≥ r.y:
        - Sort Lpts and Rpts by descending y (tie‐break ascending x).
        - Maintain two deques (vectors) paretoL and paretoR, each storing points in strictly increasing x order.
        - Use a pointer i over Lpts. For each r in Rpts in descending‐y order:
           • Pop from paretoR any points with x > r.x.
           • Add all Lpts[i] with y≥r.y into paretoL, popping from paretoL any with x≤ new point's x (to keep it a true Pareto frontier).
           • Now every ℓ in paretoL is a valid friend‐partner for r, so add paretoL.size() to ans.
           • But some ℓ may have already been matched to a previous R‐point of higher y (and so that rectangle would have contained that earlier R). We subtract the count of those ℓ whose y≥ paretoR.back().y (if paretoR is nonempty).
           • Finally push r into paretoR.
     c. SWEEP #2 for ℓ.y ≤ r.y:
        - Sort Lpts and Rpts by ascending y (tie‐break ascending x).
        - Clear paretoL and paretoR, reset pointer i over Lpts.
        - For each r in Rpts in ascending‐y order:
           • Pop from paretoR any with x > r.x.
           • Add all Lpts[i] with y≤r.y into paretoL, popping dominated ones by x.
           • If paretoR is empty, all in paretoL have y<r.y, so add the count of ℓ with y<r.y.
             Otherwise subtract those ℓ with y≤ paretoR.back().y.
           • Push r into paretoR.
     d. Add the two sweep counts to ans.

  Return ans.

This runs in O(n log² n) overall for n≤10⁵.

4. C++ implementation with comments

```cpp
#include <bits/stdc++.h>
using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
}

int n;
map<int, vector<pair<int, int>>> pts_by_x;

int64_t divide_conquer(vector<vector<pair<int, int>>>& pnts) {
    if(pnts.size() == 1) {
        return pnts[0].size() - 1;
    }

    vector<vector<pair<int, int>>> l_rec, r_rec;
    vector<pair<int, int>> left_pts, right_pts;

    int mid = pnts.size() / 2;
    for(int i = 0; i < mid; ++i) {
        for(auto& pt: pnts[i]) {
            left_pts.push_back(pt);
        }
        l_rec.push_back(pnts[i]);
    }
    for(int i = mid; i < (int)pnts.size(); ++i) {
        for(auto& pt: pnts[i]) {
            right_pts.push_back(pt);
        }
        r_rec.push_back(pnts[i]);
    }

    int64_t result = 0;

    sort(
        left_pts.begin(), left_pts.end(),
        [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.second > b.second ||
                   (a.second == b.second && a.first < b.first);
        }
    );
    sort(
        right_pts.begin(), right_pts.end(),
        [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.second > b.second ||
                   (a.second == b.second && a.first < b.first);
        }
    );

    vector<pair<int, int>> pareto_left;
    vector<pair<int, int>> pareto_right;
    auto left_ptr = left_pts.begin();

    for(auto& curr: right_pts) {
        while(!pareto_right.empty() && pareto_right.back().first > curr.first) {
            pareto_right.pop_back();
        }

        while(left_ptr != left_pts.end() && left_ptr->second >= curr.second) {
            while(!pareto_left.empty() &&
                  pareto_left.back().first <= left_ptr->first) {
                pareto_left.pop_back();
            }
            pareto_left.push_back(*left_ptr);
            ++left_ptr;
        }

        result += pareto_left.size();
        if(!pareto_right.empty()) {
            auto it = upper_bound(
                pareto_left.begin(), pareto_left.end(),
                pareto_right.back().second,
                [](int y, const pair<int, int>& p) { return y > p.second; }
            );
            result -= (it - pareto_left.begin());
        }

        pareto_right.push_back(curr);
    }

    sort(
        left_pts.begin(), left_pts.end(),
        [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.second < b.second ||
                   (a.second == b.second && a.first < b.first);
        }
    );
    sort(
        right_pts.begin(), right_pts.end(),
        [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.second < b.second ||
                   (a.second == b.second && a.first < b.first);
        }
    );

    pareto_left.clear();
    pareto_right.clear();
    left_ptr = left_pts.begin();

    for(auto& curr: right_pts) {
        while(!pareto_right.empty() && pareto_right.back().first > curr.first) {
            pareto_right.pop_back();
        }

        while(left_ptr != left_pts.end() && left_ptr->second <= curr.second) {
            while(!pareto_left.empty() &&
                  pareto_left.back().first <= left_ptr->first) {
                pareto_left.pop_back();
            }
            pareto_left.push_back(*left_ptr);
            ++left_ptr;
        }

        if(pareto_right.empty()) {
            auto it = upper_bound(
                pareto_left.begin(), pareto_left.end(), curr.second - 1,
                [](int y, const pair<int, int>& p) { return y < p.second; }
            );
            result += (it - pareto_left.begin());
        } else {
            auto it1 = upper_bound(
                pareto_left.begin(), pareto_left.end(), curr.second - 1,
                [](int y, const pair<int, int>& p) { return y < p.second; }
            );
            auto it2 = upper_bound(
                pareto_left.begin(), pareto_left.end(),
                pareto_right.back().second,
                [](int y, const pair<int, int>& p) { return y < p.second; }
            );
            result +=
                max(0ll, (int64_t)(it1 - pareto_left.begin()) -
                             (it2 - pareto_left.begin()));
        }

        pareto_right.push_back(curr);
    }

    result += divide_conquer(l_rec) + divide_conquer(r_rec);
    return result;
}

void read() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        pts_by_x[x].push_back({x, y});
    }
}

void solve() {
    // For a given point (x, y), let's try to find the "pareto front" of the
    // points to the left and below it. Then number of friends is the number of
    // points in this pareto front + number of points in a similar pareto front
    // above and to the left of it. Unfortunately, this is hard to maintain
    // dynamically, but we can use a divide and conquer approach:
    // 1. Get median point by x coordinate.
    // 2. Split the points into two halves, left and right of the median, and
    //    recursively find the number of pairs in each half.
    // 3. For each point in the left half, count how many points in the right
    //    half make a pair with it.
    //
    // For (3), we can sort by y coordinate and then do a merge-sort like
    // procedure. In particular for a point on the right side, we are interested
    // in the size of the "pareto front" on the left side above this point. The
    // only thing we should be careful about is that for point (i) on the right
    // side, we can only look at the pareto front with y >=
    // y_of_right_point(i-1), because otherwise point (i-1) would be inside of
    // the rectangle. However, this is still a range and can be found with
    // binary search.
    //
    // This solution is O(N log^2 N) but the inner logarithm is very light.

    vector<vector<pair<int, int>>> pnts;
    for(auto it: pts_by_x) {
        pnts.push_back(it.second);
    }

    int64_t result = divide_conquer(pnts);
    cout << result << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with detailed comments

```python
import sys
import threading
from bisect import bisect_left, bisect_right

def main():
    sys.setrecursionlimit(10**7)
    data = sys.stdin.read().split()
    n = int(data[0])
    pts = []
    idx = 1
    for i in range(n):
        x = int(data[idx]); y = int(data[idx+1])
        idx += 2
        pts.append((x,y))
    # Group by x-coordinate
    from collections import defaultdict
    groups = defaultdict(list)
    for x,y in pts:
        groups[x].append((x,y))
    # Sort groups by x
    pnts = [groups[x] for x in sorted(groups)]

    # Divide & conquer
    def dc(pnts):
        m = len(pnts)
        # Base: if all share one x, friendly pairs = (#points-1)
        if m == 1:
            return len(pnts[0]) - 1

        mid = m // 2
        left_groups = pnts[:mid]
        right_groups = pnts[mid:]

        # Flatten left and right
        left_flat = [pt for g in left_groups for pt in g]
        right_flat = [pt for g in right_groups for pt in g]

        ans = 0

        # ---- Sweep 1: left.y >= right.y ----
        # Sort by descending y, then ascending x
        left_flat.sort(key=lambda p:(-p[1], p[0]))
        right_flat.sort(key=lambda p:(-p[1], p[0]))

        pareto_left = []   # will store (x,y) with x strictly increasing
        pareto_right = []  # same for right
        li = 0             # pointer into left_flat

        for rx, ry in right_flat:
            # maintain pareto_right: keep x increasing
            while pareto_right and pareto_right[-1][0] > rx:
                pareto_right.pop()
            # add all left points with y>=ry
            while li < len(left_flat) and left_flat[li][1] >= ry:
                lx, ly = left_flat[li]
                # remove dominated: keep x strictly increasing
                while pareto_left and pareto_left[-1][0] <= lx:
                    pareto_left.pop()
                pareto_left.append((lx, ly))
                li += 1
            # all current pareto_left can pair with (rx,ry)
            ans += len(pareto_left)
            # subtract those that already paired with an earlier right
            if pareto_right:
                # count how many in pareto_left have y >= pareto_right[-1].y
                ry0 = pareto_right[-1][1]
                lo, hi = 0, len(pareto_left)
                while lo < hi:
                    mid2 = (lo+hi)//2
                    if pareto_left[mid2][1] >= ry0:
                        lo = mid2 + 1
                    else:
                        hi = mid2
                ans -= lo
            # add current right to its Pareto frontier
            pareto_right.append((rx, ry))

        # ---- Sweep 2: left.y <= right.y ----
        # Sort by ascending y, then ascending x
        left_flat.sort(key=lambda p:(p[1], p[0]))
        right_flat.sort(key=lambda p:(p[1], p[0]))

        pareto_left.clear()
        pareto_right.clear()
        li = 0

        for rx, ry in right_flat:
            while pareto_right and pareto_right[-1][0] > rx:
                pareto_right.pop()
            while li < len(left_flat) and left_flat[li][1] <= ry:
                lx, ly = left_flat[li]
                while pareto_left and pareto_left[-1][0] <= lx:
                    pareto_left.pop()
                pareto_left.append((lx, ly))
                li += 1

            if not pareto_right:
                # count all with y < ry
                ys = [p[1] for p in pareto_left]
                idx2 = bisect_left(ys, ry)
                ans += idx2
            else:
                # subtract those paired earlier
                ys = [p[1] for p in pareto_left]
                idx1 = bisect_left(ys, ry)
                y0 = pareto_right[-1][1]
                idx2 = bisect_right(ys, y0)
                ans += max(0, idx1 - idx2)

            pareto_right.append((rx, ry))

        # recurse on halves
        return ans + dc(left_groups) + dc(right_groups)

    print(dc(pnts))


if __name__ == "__main__":
    main()
```

Explanation of key parts:
- We split the x‐ordered groups in half and recurse.
- Counting cross‐pairs reduces to two "sweeps" over the right‐half points sorted by y, maintaining a Pareto frontier of left‐half points by strictly increasing x.
- Each sweep runs in O(|L|+|R|) time. The total recurrence is T(n) = 2 T(n/2) + O(n log n), giving O(n log² n) for n up to 10⁵.
