Memory limit: 64 MB
Bytie has got a set of wooden blocks for his birthday. The blocks are indistinguishable from one another, as they are all cubes of the same size. Bytie forms piles by putting one block atop another. Soon he had a whole rank of such piles, one next to another in a straight line. Of course, the piles can have different heights.
Bytie's father, Byteasar, gave his son a puzzle. He gave him a number and asked to rearrange the blocks in such a way that the number of successive piles of height at least is maximised. However, Bytie is only ever allowed to pick the top block from a pile strictly higher than and place it atop one of the piles next to it. Further, Bytie is not allowed to form new piles, he can only move blocks between those already existing.
In the first line of the standard input there are two integers separated by a single space: (), denoting the number of piles, and (), denoting the number of Byteasar's requests. The piles are numbered from to . In the second line there are integers separated by single spaces (). The number denotes the height of the -th pile. The third line holds integers separated by single spaces (). These are the subsequent values of the parameter for which the puzzle is to be solved. That is, the largest number of successive piles of height at least that can be obtained by allowed moves is to be determined for each given value of the parameter .
Your program should print out integers, separated by single spaces, to the standard output - the -th of which should be the answer to the puzzle for the given initial piles set-up and the parameter .
For the input data:
5 6 1 2 1 1 5 1 2 3 4 5 6
the correct result is:
5 5 2 1 1 0
Task author: Jacek Tomasiewicz.<Submit a solution> [0/100]