
ZOJ Problem Set  2451
The company Chris Ltd. is preparing a new sorting hardware called Maximizer. Maximizer has N inputs numbered from 1 to N. Each input represents one integer. Maximizer has one output which represents the maximum value present on Maximizer's inputs. Maximizer is implemented as a pipeline of sorters Sorter(i[1], j[1]), ..., Sorter(i[k], j[k]). Each sorter has N inputs and N outputs. Sorter(i, j) sorts values on inputs i, i+1, ..., j in nondecreasing order and lets the other inputs pass through unchanged. The Nth output of the last sorter is the output of the Maximizer. An intern (a former ACM contestant) observed that some sorters could be excluded from the pipeline and Maximizer would still produce the correct result. What is the length of the shortest subsequence of the given sequence of sorters in the pipeline still producing correct results for all possible combinations of input values? Task Write a program that:
Input SpecificationThe input consists of several test cases. Output SpecificationFor each test case, print in one line the length of the shortest subsequence of the initial sequence of sorters still producing correct results for all possible data. Sample Input40 6 20 30 1 10 10 20 20 30 15 25 30 40 Output for the Sample Input4
Source: Central Europe 2003 