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

有一个由 $N$ 个整数组成的序列 $a_1,a_2, \cdots ,a_N$。序列 $b_1,b_2, \cdots ,b_L$ 是给定序列的子序列，如果 1. 对于每个 $i$ （$1 \leq i \leq L$），存在这样的 $j$ （$1 \leq j \leq N$），使得 $b_i= a_j$； 1. 对于每个 $i_1$ 和 $i_2$ 使得 $i_1 < i_2$，$b_{i1} = a_{j1}$，$b_{i2} = a_{j2}$，关系 $j_1 < j_2$ 是有效的。 序列 $b_1,b_2, \cdots,b_L$ 是非递增的，如果对于每个 $i$（$1 \le i < L$），$b_i \le b_{i+1}$。 序列 $b_1,b_2, \cdots,b_L$ 是非递减的，如果对于每个 $i$（$1 \le i < L$），$b_i \le b_{i+1}$。 给定的序列称为 **NICE**，如果我们可以选择该序列的 $K$ 个子序列使得： 1. 每个子序列至少有 $2$ 个成员， 1. 每个子序列要么不增加要么不减少， 1. 给定序列的每个成员直接属于一个子序列。 找出给定序列的最小可能 $K$。

第一行包含一个整数为 $N$ 的值，接下来的 $N$ 行包含序列成员的值（每行一个整数，对于每个 $j$（$1 \le a_j \le 100$））。

输出数据必须包含： 1. 第一行中 $K$ 的值， 1. 将给定序列划分为 $K$ 个子序列的一个示例（即必须有 $N$ 行，每行包含子序列的 $a_j$ 和其 $a_j$ 属于的 索引（$1 \le$ 索引 $\le K$））。 如果给定的序列不是 **NICE**，则输出文件的第一行必须仅包含 $0$。

#### 数据规模与约定 对于 $100 \%$ 的数据，$1 \le N \le 25$，$0 < K \le N$。 #### 样例说明 样例一中，子序列是 $12，33，33$ 和 $97，18，15$。 #### 分值说明 本题分值按 BOI 原题设置，**满分** $40$ 。 #### 题目说明 来源于 Baltic Olympiad in Informatics 2000] 的 [Day 1:A NICE SEQUENCE](https://boi.cses.fi/files/boi1996_day1.pdf)。 由 @[求学的企鹅](/user/271784) 翻译整理。