410480: GYM104025 F ZYW with books
Description
ZYW has too many books to organize! But he has already set up a flag in front of his roommates that he will finish sorting out his books tonight. Each book of ZYW has an attribute $$$a_i$$$ to describe the usage frequency of the book. The smaller the $$$a_i$$$, the higher usage frequency. ZYW hopes to make books with high usage frequency in front of books with low usage frequency. But now the books on the shelf are out of order.
Sadly, ZYW has a very serious obsessive-compulsive disorder. He can only take a book from the front of the shelf or put a book in the back of the shelf, while inserting or taking out a book from any other position is prohibited. ZYW also made space to organize books. Books can be stacked here, that is, he can put a book at the top or take a book from the top.
Now the deadline is coming. ZYW hopes you can help him plan how to organize his books.
Specifically, there are $$$n$$$ books on ZYW's bookshelf, and each book has the attribute $$$a_i$$$ to describe its frequency of use. ZYW can perform one of the following two operations at a time:
- Take a book from the front of the shelf and put it on the top of the book stack.
- Take a book from the top of the book stack and put it on the back of the shelf.
The first line contains an integer $$$n\ (1\le n\le 10^5)$$$, the number of books.
The next line contains $$$n$$$ integers, the $$$i$$$-th integer $$$a_i\ (0\le a_i\le 10^9)$$$ describes the usage frequency of the $$$i$$$-th book. The input order is from front to back.
OutputThe first line contains a single integer $$$k$$$, representing the number of operations. Note that $$$k$$$ should not exceed $$$40\times n$$$.
In the second line, print a string of length $$$k$$$ consisting of $$$1$$$ and $$$2$$$, representing your operation type in order.
ExampleInput5 3 2 4 5 1Output
8 11221212