Description

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$;
2. 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;
2. Each subsequence is either non-increasing or non-decreasing;
3. Every element of the given sequence belongs to exactly one subsequence.

Find the minimum possible $K$ for the given sequence.

Input Format

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$).

Output Format

The output must contain:

1. The value of $K$ in the first line;
2. 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$.

6
12
33
97
18
15
33

2
12 1
33 1
97 2
18 2
15 2
33 1

1
88

0

4
77
22
22
11

1
77 1
22 1
22 1
11 1

Hint

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 in Baltic Olympiad in Informatics 1996.
Translated and整理 (zhěng lǐ: organized) by @求学的企鹅.

Translated by ChatGPT 5