p133.ans1
======================
3

=================
p133.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;
vector<pair<int, int>> a;

void read() {
    cin >> n;
    a.resize(n);
    cin >> a;
}

void solve() {
    /*
     * Outpost i is redundant iff some j has A[j] < A[i] and B[i] < B[j]. Sort
     * the intervals by left endpoint A ascending; then while scanning we track
     * mx = the largest right endpoint B among all already-seen outposts (which
     * all have strictly smaller A). The current outpost is redundant exactly
     * when its B is below mx. All A and all B are distinct, so no ties matter.
     */

    sort(a.begin(), a.end());
    int answer = 0;
    int mx = INT_MIN;
    for(int i = 0; i < n; i++) {
        if(a[i].second < mx) {
            answer++;
        }

        mx = max(mx, a[i].second);
    }

    cout << answer << '\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;
}

=================
p133.in1
======================
5
0 10
2 9
3 8
1 15
6 11

=================
statement.txt
======================
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

=================
