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 soldieimgr V'(x', y') such that x <= x' and y <= y', i.e. if there exists no other soldier that is "above-right" 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 xi and yi, representing the coordinates of Nikolaj's i-th 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)}.

Front

Constraints

  • 1 <= N <= 106
  • 0 <= xi, yi <= 109
  • No pair of soldiers will share the same position.
  • The soldiers will be sorted ascending by their x coordinate, i.e. x1 <= x2 <= ... <= xN.

Added by:PetarV
Date:2015-04-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Serbian Regionals 2015 (Own problem)

hide comments
2024-06-11 05:36:55
apparently, the data is not in a sorted state
2019-01-11 04:37:01
Do not sort points and use scanf instead of cin >> ...
2016-10-13 19:54:53
What is the expected time limit ? Using map causes TLE so I guess O(nlog(n)) is not accepted ?
2016-07-17 12:57:57
Please check my solution .

Last edit: 2016-07-17 12:58:09
2016-07-16 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.
2015-08-03 22:50:59 Baojun Wang
non-standard EOF, seems end of input /= '\n' EOF
2015-07-20 19:10:09 Diksha Jaiswal
AC in 1 go :)
2015-06-11 03:21:04 gamer496
@admin yes I know that and have taken into consideration.My logic is based on x-coordinate being sorted and y-cord 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.

Re (PetarV):
Your code is immediately discarding the x-coordinate information, but it is potentially important later on (it is very easy to construct a test case that causes WA---I will let you think of it on your own. Good luck!).

Last edit: 2015-06-14 05:22:49
2015-05-29 06:28:28 Daksh
nice :) :)
2015-05-20 08:14:18 pingal tirkey
Yup! graph solved half of the problem!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.