FRONT  Front
Little Petar is playing a strategic warfare game against his opponent, Little Nikolaj. In the game, two players compete for supremacy over the opponent's base. The bases are located at the opposite ends of the map (Nikolaj's in the lower left corner of the map, Petar's in the upper right corner) and may be attacked or defended with the use of soldiers (that are at any time located at a given (x, y) coordinate pair on the map).
Petar has looked at Nikolaj's screen at a critical moment and successfully noted down all the positions where Nikolaj placed his soldiers, sorted in ascending order by the x coordinate. In order to plan an efficient attack, Petar is now interested in knowing how many of Nikolaj's soldiers are most vulnerable (i.e. located on the "frontline").
A soldier V(x, y) is located on the frontline if there is no other soldier V'(x', y') such that x <= x' and y <= y', i.e. if there exists no other soldier that is "aboveright" from that soldier.
Input
The first line of the standard input contains a natural number N, representing the number of Nikolaj's soldiers. Each of the following N lines contains two integers x_{i} and y_{i}, representing the coordinates of Nikolaj's ith soldier. The soldiers will be sorted ascending by their x coordinate.
Output
Write to the standard output a single line containing the integer F, the number of Nikolaj's soldiers located on the frontline.
Example
Input:
6
0 1
1 5
3 5
3 2
4 4
5 1
Output: 3
Explanation
The positions of Nikolaj's soldiers from the given testcase are shown on the image below. The frontline is marked with the red line and consists of the following set of soldiers: {(3, 5), (4, 4), (5, 1)}.
Constraints
 1 <= N <= 10^{6}
 0 <= x_{i}, y_{i} <= 10^{9}
 No pair of soldiers will share the same position.
 The soldiers will be sorted ascending by their x coordinate, i.e. x_{1} <= x_{2} <= ... <= x_{N}.
hide comments
smso:
20190111 04:37:01
Do not sort points and use scanf instead of cin >> ... 

dwij28:
20161013 19:54:53
What is the expected time limit ? Using map causes TLE so I guess O(nlog(n)) is not accepted ? 

wano:
20160717 12:57:57
Please check my solution . Last edit: 20160717 12:58:09 

azam_9:
20160716 20:23:19
@author can u plz check my code..it gives same output for every test case as on spojtoolkit still getting W.A. 

Sushovan Sen:
20160513 22:05:43
Last edit: 20160513 22:25:36 

Baojun Wang:
20150803 22:50:59
nonstandard EOF, seems end of input /= '\n' EOF 

Diksha Jaiswal:
20150720 19:10:09
AC in 1 go :) 

gamer496:
20150611 03:21:04
@admin yes I know that and have taken into consideration.My logic is based on xcoordinate being sorted and ycord not.I've tried several different test cases including the ones given here and the ones I made on my own and the program is running fine.


Daksh:
20150529 06:28:28
nice :) :) 

pingal tirkey:
20150520 08:14:18
Yup! graph solved half of the problem! 
Added by:  PetarV 
Date:  20150407 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 
Resource:  Serbian Regionals 2015 (Own problem) 