Problem Description

There is a sequence consisting of $N$ integers $a_1, a_2, \cdots, a_N$. A subsequence $b_1, b_2, \cdots, b_L$ of the given sequence is defined if:
1. For each $i$ ($1 \leq i \leq L$), there exists such $j$ ($1 \leq j \leq N$) that $b_i = a_j$;
2. For each $i_1$ and $i_2$ such that $i_1 < i_2$, $b_{i1} = a_{j1}$, $b_{i2} = a_{j2}$, the relation $j_1 < j_2$ holds.

The sequence $b_1, b_2, \cdots, b_L$ is non-increasing if for each $i$ ($1 \leq i < L$), $b_i \geq b_{i+1}$. The sequence $b_1, b_2, \cdots, b_L$ is non-decreasing if for each $i$ ($1 \leq i < L$), $b_i \leq b_{i+1}$.

The given sequence is called NICE if we can select $K$ subsequences from it such that:
1. Each subsequence has at least 2 members,
2. Each subsequence is either non-increasing or non-decreasing,
3. Each member of the given sequence directly belongs to one subsequence.

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

Input Format

The first line contains the value of $N$, followed by $N$ lines each containing a value of the sequence members (each integer $a_j$ where $1 \leq a_j \leq 100$).

Output Format

The output data must include:
1. The value of $K$ on the first line,
2. An example of partitioning the given sequence into $K$ subsequences (there must be $N$ lines, each containing the value $a_j$ and the index of the subsequence it belongs to ($1 \leq$ index $\leq K$)).

If the given sequence is not NICE, the first line of the output file must contain only $0$.

Sample Input and Output

Sample Input #1

6
12
33
97
18
15
33

Sample Output #1

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

Sample Input #2

1
88

Sample Output #2

0

Sample Input #3

4
77
22
22
11

Sample Output #3

1
77 1
22 1
22 1
11 1

Notes

Data Size and Constraints

For $100\%$ of the data, $1 \leq N \leq 25$, $0 < K \leq N$.

Sample Explanation

In Sample #1, the subsequences are $12, 33, 33$ and $97, 18, 15$.

Score Explanation

This problem is set according to the original BOI configuration, with a full score of $40$.

Problem Source

Derived from Baltic Olympiad in Informatics 2000, Day 1: A NICE SEQUENCE. Translated and arranged by @求学的企鹅.

见题面 Input 部分

见题面 Output 部分