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.
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.
You should print the number of redundant outposts.
: Mugurel Ionut Andreica
: SSU::Online Contester Fall Contest #2
: Fall 2002
Codeforces (c) Copyright 2010-2019 Mike Mirzayanov