November 6, 1999 -- Problem 7
1999 ACM Programming Contest Mid-Atlantic Region
The Internet Bubble


The DOTCOM organization evaluates internet stocks by looking at the price of their stock at regular intervals. They do not expect any stock to consistently increase in value, but instead look at longer-term trends. In particular, they are trying to determine, from a sequence of prices, the longest subsequence of values for which each price is higher than the previous one. In doing so, it is acceptable to ignore all prices between two values as long as the first price in the comparison is less than the second price in the comparison.

Consider the following example: for the string of numbers

 1 10 2 10 3 10 4 10 5 10 7 6 8 
The longest increasing subsequence has length 7, composed of
 1 2 3 4 5 7 8 

The DOTCOM organization considers a stock to have reached YAHOOIAN proportions when its sequence of values has a subsequence of 1000 increasing entries. Your program should determine YAHOOIAN stocks from day-to-day price sequences and should determine how close non-YAHOOIAN stocks are.


The input file will consist of one or more data set, which are whitespace-separated lists of integers that represent the day-to-day prices of a particular stock. The data set will terminate with a value less than 0 (this terminating value should be ignored, though in the current market it may well reflect the company's capitalization...). All of the integers will fit into signed ints. There is no limit to the length of the input data sets.


For each input data set, there should be one line of output. If the data set contains a subsequence of 1000 (or more) increasing values, the output line should be

The stock has reached YAHOOIAN proportions.
Otherwise, the output line should be
The stock has an increasing subsequence of maximum length N.
where N should be replaced by the appropriate length (0 < N < 1000).

Sample Input

1 10 2 10 3 10 4 10 5 10 7 6 8 -1 1 2 3 (4 through 998) 999 9
1000 9 -1

Sample Output

The longest subset of prices is 7.
The stock has reached YAHOOIAN proportions.