410480: GYM104025 F ZYW with books

F. ZYW with bookstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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:

1. Take a book from the front of the shelf and put it on the top of the book stack.
2. Take a book from the top of the book stack and put it on the back of the shelf.

You need to give an operation sequence so that after all operations are completed, all books should be on the shelf, and the attribute $$$a_i$$$ of them is in non-descending order from front to back. Since the deadline is approaching, the number of operations should not exceed $$$40\times n$$$.Input

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.

Output

The 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.

ExampleInput

5
3 2 4 5 1

Output

8
11221212