cho.sh
Notes
Loading...

Maximum Increasing Rectangle Set

Time limit

2s

Memory limit

128 MB

Problem

There are N axis-aligned rectangles on a coordinate plane. For each rectangle, call its lower-left vertex the start point and its upper-right vertex the end point.

You want to choose some rectangles and form a set L. For every two distinct rectangles p and q in L, one of the following conditions must hold:

  • The x-coordinate of p's end point is smaller than the x-coordinate of q's start point, and the y-coordinate of p's end point is also smaller than the y-coordinate of q's start point.
  • The x-coordinate of q's end point is smaller than the x-coordinate of p's start point, and the y-coordinate of q's end point is also smaller than the y-coordinate of p's start point.

Find the maximum number of rectangles that can be chosen while satisfying this condition.

Input

The first line contains the number of rectangles N. (1 <= N <= 100,000)

Each of the next N lines contains four integers x1, y1, x2, and y2, separated by spaces, describing one rectangle. (x1, y1) is the lower-left vertex, and (x2, y2) is the upper-right vertex.

It is always true that x1 < x2 and y1 < y2, and every coordinate is between 0 and 100,000 inclusive.

Output

Print the maximum number of rectangles that can be included in a set satisfying the condition.