Missile

Description:

Long , long ago ,country A invented a missile system to destroy the missiles from their enemy . That system can launch only one missile to destroy multiple missiles if the heights of all the missiles form a non-decrease sequence .

But recently , the scientists found that the system is not strong enough . So they invent another missile system . The new system can launch one single missile to destroy many more enemy missiles . Basically , the system can destroy the missile from near to far . When the system is begun , it chooses one enemy missile to destroy , and then destroys a missile whose height is lower and farther than the first missile . The third missile to destroy is higher and farther than the second missile … the odd missile to destroy is higher and farther than the previous one , and the even missile to destroy is lower and farther than the previous one .

Now , given you a list of the height of missiles from near to far , please find the most missiles that can be destroyed by one missile launched by the new system .

Input:

The input contains multiple test cases .

In each test case , first line is an integer n ( 0<n<=1000 ) , which is the number of missiles to destroy . Then follows one line which contains n integers ( <=10⁹ ) , the height of the missiles followed by distance .

The input is terminated by n = 0 .

Output:

       For each case , print the most missiles that can be destroyed in one line .

Sample Input:

4
5 3 2 4
3
1 1 1
0

Sample Output:

3
1

Note:

本题由旧版NOJ导入，来源：NUPT ACM