Setting

Elephants: the grey area of the animal kingdom, and, according to the internet (although not to science), an area which thinks that we humans are rather cute. Time to solve assignments involving elephants!

Another myth about science is that the bigger they are, the smarter they are. This is, of course, not true, and your mission is to disprove this ridiculous claim. You consequently decide to analyze a collection of elephants to find the largest sequence of elephants whose weights are increasing, but whose IQ measurements are decreasing (never mind how one might even go about measuring an elephant's IQ...).

Input

The input consists of a number of lines, each specifying a test case. Each test case is specified on a single line, starting with the number of elephants \(1 \leq n \leq 1000\), followed by \(n\) pairs of numbers \(1 \leq w_i, iq_i \leq 10000\) for each elephant \(1 \leq i \leq n\) that describe that elephant's weight and IQ value. A line with \(n = 0\) marks the end of the input.

Output

For each input instance, output the length of the longest sequence of elephants such that their weight strictly increases and their IQ value strictly decreases.

Sample Input

The following sample input would be provided on two lines, but are split up here to increase readability. Each paragraph represents what would otherwise be specified on a single line.

9
6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900

0

Sample Output

4

This is challenge 10131 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.

Statistics

Difficulty (1 vote)
Average test runtime 0.39
Points (changes over time) 10
Tried by 5 users
Solved by 3 users

Global ranking

# Name Runtime Points worth
1 mascent 0.16 18
2 Mac 0.45 6
3 Dark 0.56 5