Interval Coloring

2000ms

262144K

Description:

Aryo has got a lot of intervals for his 2418th birthday. He is really excited and decided to color all these intervals with some colors. He has a simple rule for himself. He calls a coloring nice if there exists no three intervals a, b and c such that the following conditions are satisfied simultaneously:

a, b and c are colored with the same color,
$\text{[math]}$ ,
$\text{[math]}$ ,
$\text{[math]}$ .

Moreover he found out that for every intervals i and j, there is at least one point in i which isn't in j.

Given some set of intervals. You have to find the minimum number k, such that Aryo can find a nice coloring with k colors.

Input:

The first line contains a single integer n (1 ≤ n ≤ 10³), number of intervals.

The following n lines contain a interval description each. Each interval is described by two numbers s_i, e_i which are the start and end points of it ( - 10⁵ < s_i, e_i < 10⁵, s_i ≤ e_i). See samples for clarity. A square bracket stands for including of the corresponding endpoint, while a round bracket stands for excluding.

Output:

Write a single integer k — the minimum number of colors needed for a nice coloring.

Sample Input:

2
[1,2)
(3,4]

Sample Output:

Sample Input:

3
[1,3]
[2,6]
(5,7)

Sample Output:

Informação

Provedor Codeforces

Código CF100J