<|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.

133. Border

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


Along the border between states A and B there are N defence outposts. For every outpost k, the interval [Ak,Bk] which is guarded by it is known. Because of financial reasons, the president of country A decided that some of the outposts should be abandoned. In fact, all the redundant outposts will be abandoned. An outpost i is redundant if there exists some outpost j such that Aj<Ai and Bi<Bj. Your task is to find the number of redundant outposts.


Input

The first line of the input will contain the integer number N (1<=N<=16 000). N lines will follow, each of them containing 2 integers: Ak and Bk (0<= Ak < Bk <= 2 000 000 000), separated by blanks. All the numbers Ak will be different. All the numbers Bk will be different.


Output

You should print the number of redundant outposts.


Sample Input

5
0 10
2 9
3 8
1 15
6 11
Sample Output

3
Author	: Mugurel Ionut Andreica
Resource	: SSU::Online Contester Fall Contest #2
Date	: Fall 2002

<|response|>
1. Abridged Problem Statement  
You are given N intervals [Ai, Bi], with all start points Ai distinct and all end points Bi distinct. An interval i is called redundant if there exists another interval j such that Aj < Ai and Bi < Bj (i.e., interval i is strictly contained in some earlier-starting, later-ending interval j). Count how many intervals are redundant.

2. Key Observations  
- Since all Ai are distinct, we can sort intervals in strictly increasing order of Ai.  
- When processing intervals in that order, any candidate for containing the current interval must appear earlier in the sorted list.  
- Among all previously seen intervals, the one with the maximum end coordinate Bmax is the “widest.” If the current Bi < Bmax, we know there exists some previous interval j with Bj = Bmax > Bi, so the current interval is redundant.  
- Otherwise, we update Bmax to Bi and continue.  
- This yields an O(N log N) solution (sorting + single pass).

3. Full Solution Approach  
a. Read N and the list of intervals (Ai, Bi).  
b. Sort the intervals by Ai in ascending order.  
c. Initialize:  
   • Bmax = −∞ (to track the largest end among processed intervals)  
   • answer = 0 (count of redundant intervals)  
d. For each interval (Ai, Bi) in the sorted list:  
   1. If Bi < Bmax, increment answer (interval is redundant).  
   2. Else, set Bmax = Bi (this interval extends the maximum coverage).  
e. After the loop, output answer.

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

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

    int N;
    cin >> N;
    vector<pair<long long, long long>> intervals(N);

    // Read all intervals
    for (int i = 0; i < N; i++) {
        cin >> intervals[i].first >> intervals[i].second;
    }

    // Sort by start point Ai ascending
    sort(intervals.begin(), intervals.end(),
         [](auto &a, auto &b) { return a.first < b.first; });

    long long Bmax = LLONG_MIN;  // maximum end seen so far
    int answer = 0;               // count of redundant intervals

    // Sweep through intervals in sorted order
    for (auto &iv : intervals) {
        long long Bi = iv.second;
        // If the current interval ends before the widest seen so far,
        // it is strictly contained in some previous interval
        if (Bi < Bmax) {
            answer++;
        } else {
            // Otherwise update the widest end
            Bmax = Bi;
        }
    }

    // Output the total number of redundant intervals
    cout << answer << "\n";
    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))

    # Read intervals into a list of tuples
    intervals = []
    for _ in range(n):
        a = int(next(it))
        b = int(next(it))
        intervals.append((a, b))

    # Sort by the start coordinate a ascending
    intervals.sort(key=lambda x: x[0])

    Bmax = -10**18  # largest end seen so far
    answer = 0      # count of redundant intervals

    # Process intervals in sorted order
    for a, b in intervals:
        # If this interval ends before Bmax,
        # some previous interval covers it entirely
        if b < Bmax:
            answer += 1
        else:
            # Otherwise update the maximum end seen
            Bmax = b

    # Print the result
    print(answer)

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