P7652 [BalticOI 1996] A NICE SEQUENCE (Day 1)

There is a sequence $a_1, a_2, \cdots, a_N$ consisting of $N$ integers. A sequence $b_1, b_2, \cdots, b_L$ is a subsequence of the given sequence if: 1. For each $i$ ($1 \le i \le L$), there exists a $j$ ($1 \le j \le N$) such that $b_i = a_j$; 1. For any $i_1$ and $i_2$ with $i_1 < i_2$, if $b_{i1} = a_{j1}$ and $b_{i2} = a_{j2}$, then the relation $j_1 < j_2$ holds. The sequence $b_1, b_2, \cdots, b_L$ is non-increasing if for every $i$ ($1 \le i < L$), $b_i \ge b_{i+1}$. The sequence $b_1, b_2, \cdots, b_L$ is non-decreasing if for every $i$ ($1 \le i < L$), $b_i \le b_{i+1}$. The given sequence is called **NICE** if we can choose $K$ subsequences of this sequence such that: 1. Each subsequence has at least $2$ elements; 1. Each subsequence is either non-increasing or non-decreasing; 1. Every element of the given sequence belongs to exactly one subsequence. Find the minimum possible $K$ for the given sequence.

The first line contains an integer $N$. The next $N$ lines contain the elements of the sequence (one integer per line, and for each $j$, $1 \le a_j \le 100$).

The output must contain: 1. The value of $K$ in the first line; 1. One example of a partition of the given sequence into $K$ subsequences (that is, there must be $N$ lines, each containing $a_j$ and the index ($1 \le$ index $\le K$) of the subsequence to which $a_j$ belongs). If the given sequence is not **NICE**, then the first line of the output must contain only $0$.

#### Constraints For $100\%$ of the testdata, $1 \le N \le 25$, $0 < K \le N$. #### Sample Explanation In sample 1, the subsequences are $12, 33, 33$ and $97, 18, 15$. #### Scoring The score of this problem follows the original BOI settings, with a **full score** of $40$. #### Notes This problem comes from [Day 1: A NICE SEQUENCE](https://boi.cses.fi/files/boi1996_day1.pdf) in Baltic Olympiad in Informatics 1996. Translated and整理 (zhěng lǐ: organized) by @[求学的企鹅](/user/271784). Translated by ChatGPT 5