Description

Mark Stockle has taken interest in analyzing the stock market. Recently, he has focused on a particular company’s stock. He observes the price of this stock over a period of N days. Then, he stares at these numbers for a long time and tries to identify the patterns and trends in the price. For example, he might notice that near the beginning of the N days, the price was decreasing, but then it steadily rising later. Or he might notice that generally the price was going up with the occasional daily dip. However, he was unable to come up with any rigorous or general approach for analyzing the stock.

One day, his friend suggested the following strategy: he ought to break up the problem of explaining N days of prices into smaller manageable subproblems. In particular, he would divide up the N days into K sets, and explain each set using a single hypothesis. Note that the days in a set do not have to be contiguous.

In his machine learning class, Mark learned the power of Occam’s Razor, which was that simple hypotheses that explain the data tend to generalize better on future data. It was so important for him to have simple hypotheses that he only allowed two types of hypotheses: that the prices of the stock on the days in a set would not increase or not decrease over time. Of course, there must be at least two days per set, since it does not make sense to explain the stock price of one day by itself. Lastly, the most important method to impose simplicity was to have as few hypotheses as possible, i.e. minimize K.

Input

The first line contains N (1 ≤ N ≤ 30), the number of days for which Mark has collected stock prices. The next N lines contain N integers in the range [0, 100], one on each line. These integers represent the stock prices over N days.

Output

On a single line, output K, the minimum number of hypotheses needed to explain the stock data. If it is impossible to explain the data using K hypotheses as described above, simply output 0.

8
1
6
3
5
4
2
7
0

2

Source

MIT Programming Contest 2005