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
2015-04-26 09:03:42 mkrjn99
This question could have caused some trouble if you didn't give that figure!
2015-04-19 08:41:53 Akhilesh Anandh
Much easier than it looks :)

Last edit: 2015-04-19 13:05:21
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.