L is a rather sluttish guy. He almost never clean up his surroundings or regulate his personal goods, and often can't find them at need. What's worse, due to his power of impact in his dorm, not only is he himself sluttish, but he also spreads the habit of sluttery to his roommates. Even those who were originally pretty well-regulated, such as Song, has been affected by him, and seldom do any cleaning.
As a result, L often can't find his book before class, and thus has to suffer from an out-of-book class, during which he often sleeps and wastes time. After this has happend hundreds of times, L finally made a great effort to decide to tidy up his bookshelf. He collected all his books from everywhere in his dorm ---- under the beds, on the windowsill, inside the desks......, put them in a huge box, and began to place the books onto his bookshelf. To make his bookshelf look more smart, L decided to arrange his books such that their height on the bookshelf increases(at least not decrease) from left to right. (i.e.the shortest book is on the left,and as one moves towards the right end of the bookshelf the books' heights either remain the same as the previous book or increase, until the rightmost book is reached which is the tallest on the shelf).
This seems a very easy, albeit time-consuming, task. Unfortunately, L has a strange way of putting his books on the shelf. As he takes a book out of the box, he wants to put it on the shelf without moving any of his other books(he is too lazy to do that), and the books should still be arranged in an acceptable way. For each book, he can either put it on the shelf, or put it aside (i.e.not put it on the shelf): if he puts it aside,then he will never put that book on the shelf. In other words, for every book, L may only put the book on the left side, or on the right side of the bookshelf. He may also throw this book away and not put it on the shelf.
Here is an example
Suppose L's box contains 5 books, with the following heights:
2 5 1 3 4
Books are drawn strictly from left to right,then the best number of books that L can fit on the shelf is 4. There are two possible ways of doing this:
2 3 4 5
1 3 4 5
In the first case, L puts the book with height 2 on the left side of the shelf. The book with height 5 goes to the right side. The book with height 1 can't be placed on the shelf (since it would be shorter than the book with height 2, and so would ruin the arrangement).The book with height 3 goes to the left side,and then the book with height 4 can go either to the left or right side.
In the second case, L could put the book with height 2 aside.Then he places the book with height 5 on the right side, the book with height 1 on the left side, the book with height 3 on the left side, and the book with height 4 on either the left or right side.
Input consists of a series of data sets, followed by a negative integer, which implies the end of input and should not be processed. Each data set begins with a line containing an integer N, denoting the number of books in L's box. The following line consists of N positive integers denoting the height of each book in the box. The order in which these heights are given is the order in which L takes books from the box. You may assume that 1 ¡Ü N ¡Ü 100 and the height of each book will be in the range [1,100].
For each data set in the input, output a single line containing the sentence "At most X books can be put onto the bookshelf.", where X is the maximum number of books L can put onto his bookshelf.
5 2 5 1 3 4 8 1 8 3 6 5 4 7 2 -1Sample Output
At most 4 book(s) can be put onto the bookshelf. At most 6 book(s) can be put onto the bookshelf.