VARYINGFOCUS - Varying Focus

no tags 

Daniel is taking a Computacional Vision course and decided to reproduce an interesting work that he saw at class: he took some photos of a same scene, varying just the focus, for later to combine them in just one photo, in which all the objects in scene are clear together. For that, he needs that each object seem clearly in at least one photo.

Daniel knows that for each object, there is a closed interval of focus plans in which that object stays clearly visible. For example, in the picture below, (i), (ii) and (iii) are tree photos of the same scene, each one taken with a different focus; (iv) is the combined image generated by Daniel.

 

As the memory card of Daniel's camera has a small capacity, he asked for your help. Given the intervals of focus of all the objects in the scene that he pretends to photograph, determine the minimum number of photos that he should take so that each object stays clear in at least one of the pictures.

Input

There will be at most 30 test cases. Each test case starts with a line containing one integer N, representing the number of people that used the escalator on that day (1 ≤ N ≤ 100).
On the next line, there will be N distinct integers, given in ascending order, representing the time t at which each person arrived at the escalator (1 ≤ t ≤ 1000).
The last test case is indicated when N = 0, which should not be processed.

The input consists in several case tests. The first line of each test case contains one integer N (1 ≤ N ≤ 106 ) that indicates the number of objects in the scene. Each one of the N next lines contains two integers, A and B (1 ≤ AB ≤ 109), that indicates the extremes of the focus interval of each object.

 

Output

For each test case, you should print one line with a integer that indicates the minimum number of photos that Daniel have to take.

 

Example 1

Input:
3
1 3
2 5
4 6
5
1 2
5 6
3 4
5 6
1 2

Output:
2
3

hide comments
nadstratosfer: 2018-09-27 02:06:32

Same as MAFIA.


Added by:Coach UTN FRSF
Date:2015-09-12
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY